You wouldn't necessarily have to show Dooku on the Gungan world.

Though a few AOTC shots of Lee in the Gungan city would go some way to establish his presence there and maybe the footage could be adjusted to suggest the place is under attack forcing them up onto the surface to fight.

There are plenty of rather silly looking Jedi Council members that could possibly be replaced by an actor delivering a very. very short piece of vocal exposition instead as an easier option.

Joined with a holographic message created from combining adjusted AOTC footage (and possibly a body double) with digital interference due to the transmission being partially jammed could do make it work.

You would need at least one clear shot of Dooku at the end.

Perhaps the Gungan sub could be replaced by the Queen's ship (I don't have a problem with elected monarchies as they have existed on this planet and it's an alien planet).

Luke's fighter didn't seem to like being under water but that doesn't rule out the possibility of a space craft doubling as a submarine (though the model work could be really tricky with such a shiny ship) there are plenty of cockpit shots which could be adjusted to show underwater action instead of space or cityscapes but it would be hard enough to sell without an establishing exterior shot.

It's a real shame that instead of the pointless fish fight we didn't see the droid armies invading the Gungan city and underwater battles (Star Wars meets James Bond via Jules Verne). That would have been a first for a Star Wars film But in the realms of the more possible I think the bulk of the underwater sequences are probably not salvageable (unless someone can come up with another really neat idea).