"A híd a fölött a folyó felett áll, amelyikből kiugrik egy hal." is a correct solution, so I asume that it is OK to use both "fölött" and "felett" in one adverbial phrase?
"Fölött" and "felett" are just variations, they mean exactly the same thing, they are completely interchangeable.
I know they mean the same, but "a fölött a folyó felett" seemed a bit weird to me.
Oh, I didn't notice that, sorry. I would suggest pick one and use it in both places. The postposition is supposed to be the same, even if they mean the same thing. Of course, everyone will understand, it is just a bit weird, as you say.