The conclusion that the Gungans do not have any contact with the land-dwelling Naboo does not appear to be justified, so there are no reasons to believe that the Gungans would not have had an opportunity to learn Galactic Basic. While the two groups do not appear to be cooperating all that much at the beginning of The Phantom Menace, they are clearly aware of each other, as Boss Nass's quote indicates. The Gungans have a "sacred place" (as Jar-Jar Binks puts it) on land, and Jar-Jar, having been exiled, also has taken to the land.
More specifically, Obi-Wan Kenobi points out to Nass that, "You and the Naboo form a symbiot circle. What happens to one of you will affect the other." That only makes sense if there are direct (and significant) economic, political, or social interactions between the two peoples. While Boss Nass seems to believe that the Gungans can simply hide out from the Trade Federation armies, the Jedi clearly think this is unrealistic.