Are there any nitrogen fixing plants that live in water like rice? I have problems envisaging the biochemical processes there, but I don't know much about it in the first place.

Azolla (water fern / mosquito fern).

In fact, using Azolla as rice companion plant is a long-standing practice in China: after flooding, rice paddies are seeded with Azolla, it multiplies (very) rapidly covering the surface and suppressing weeds (Azolla mats are very dense so water weeds get little to no sun) then releases nitrogen for the rice plants when it dies and rots.

Oh wow that's very interesting, thanks!