Going off of what I remember seeing in the anime, the primary issue for a lot of water Pokemon when out of water is not the issue of oxygen, but of movement. Pokemon like Magikarp and Goldeen are reduced to a state of helplessness on dry land, but do not appear to be in any danger from exposure to dry land and air, whereas Pokemon such as Milotic and Gyarados have body shapes that would facilitate much easier transport on the ground. Thus, one idea I had would be for land-based Pokemon to ferry their aquatic counterparts. This might take the form of a Mantine riding (Te)piggyback on his partner to provide covering fire and absorb any nasty water-type attacks or a Remoraid six-shooter.