Actually, you can (sort of)
Its a bit complicated and wont work all the time, but here is the gist of how it works:
Given:
RouterA with public IP 1.2.3.4
PC1 with private ip a.b.c.d (behind router A)
RouterB with public IP 5.6.7.8
PC2 with private ip e.f.g.h (behind router B)
Now, given an IDEAL solution (i.e. no PAT)...
Step A:
Send any message from PC1 on any port (10000 for this example) to the public IP for RouterB (4.5.6.7). This will register a.b.c.d:10000 -> 4.5.6.7:10000 on the NAT and PAT for routerA. RouterB will discard this packet (as expected because it wasn't requested).
Step B: At the same time, continuously send a packet from PC2 to the public IP of router A (1.2.3.4) on the same port (10000). This will register e.g.f.h:10000 -> 1.2.3.4:10000 on RouterB's NAT and PAT.
Step C:
Now, here is where the magic happens:
PC2 is constantly sending packet to RouterA thus keeping the 'hole' open in RouterB for a response to come back. When PC1 send it's single packet out to RouterB, it will appear to RouterB as a response and therefore will be forwarded to PC2. Once PC2 receives this 'response', make sure one more packet goes out and stop sending continuous packets. This last packet will act as 'response' to PC1 and go through the 'hole' created in Step A. And voila! You now have NAT transversal. You only need to send a single packet every minute or so both directions to keep the 'hole' open.
NOTE: This ONLY works with UDP as it is connectionless (dropped packets are ok).
Now almost ALL routers use PAT, so you have to 'guess' what port to 'respond' to most routers will do an offset of +-10 (i.e. a.b.c.d:10000 -> 5.6.7.8:10010).
Just try a few in that range (-10 to +10 until you get a response)
the rest of the routers are random on their PAT. If so, you're screwed... Try the other direction (i.e init the connection the other direction). If that fails, you cant connect... sorry)