In rewatching the Gungan city scenes, the real draw of the location is the location itself rather than the characters or dialogue. So how about this sequence:

-Beginning of film plays out normally, until the Jedi run into Jar Jar.
-Cut lines about Jar Jar being banished. He just leads them to the city. Cut before the captain confronts Jar Jar.
-Droid invasion of the capital and the capture of the queen.
-Bongo bursts from the underwater city with our three heroes. Splice this scene with the scene of emerging from the water at Naboo, cutting whatever fishy shenanigans you wish as well as dialogue concerning banishment.

This allows for the introduction of the pretty Gungan city with none of the stilted dialogue and bypasses the silliness of going through the planet core. Jar Jar’s life debt is still established so it is expected for him to hang around.