It's a longshot, but you might be able to make it work if you try using STUN.
The 30-second explanation of STUN:
Take two phones: A and B. Add a server, C.
A can see C. B can see C. A and B can't see each other directly.
A registers its public IP address with C. So does B.
A discovers B's public IP address from C. B discovers A's public IP address from C. Both are told to use port 6969
A and B blindly open UDP streams to each other's public IP addresses on port 6969. A starts hurling data at B's IP address, a.b.c.d. B starts hurling data at A's IP address, w.x.y.z.
Their first few bytes (or more) get silently lost, but then something magical happens. The carrier sees B sending outbound UDP to w.x.y.z:6969, and temporarily begins passing through inbound UDP arriving for a.b.c.d:6969. A's carrier does the same thing, in reverse.
Voila! A and B both see each other, as long as they keep blasting packets at each other nonstop.
It's something that's not guaranteed to work, and would probably stop working if carriers saw too many people abusing it, but occasionally you get lucky and it works. And if you can't do it between the public internet and a phone on some carrier's network, you might STILL be able to pull it off between two phones on the same carrier's network... especially if they're in the same metro area.
The key concept: you're using UDP, not TCP, so you're responsible for your own bundling, flow-control, and error-handling. The main difference is that unlike NAT, you know your own IP address, and it happens to BE your public IP as well, because you're being firewalled by the carrier, not NAT'ed. The reason doesn't matter... this is basically how services like Skype are able to punch holes through firewalls and work in places where the network owners really, really don't want it to work.
Failing that, root your phones and try Tor. There's at least one client for it in Android Market.
