There is a way that some P2P apps are starting to use:
Two clients behind firewalls connect out to a server. Each client sends to the server some a packet saying what UDP port it's going to be listening on, and what its externally visible IP address is, and the server forwards this info back to the other client. Now client A knows the IP address and port the client B will use, and vice versa.
Then the two clients start sending one another "hello are you there" packets, using the source port they've just announced, and the destination port that the other client has said that it would listen on.
So, client A sends stuff to client B, with source port pA and destination port pB. The firewall will expect response packets from client B, with destination port pA and source port pB, and prepare to forward those packets to the internal client. The other side's firewall will do the same.
Once both sides have received a "hello are you there" packet, sent back a "here I am" packet, and gotten the other side's "here I am" packet, they know they have an open connection. They just have to make sure to send packets often enough that the UDP connection won't get timed out by the firewalls.