You can solve that with STUN which is how WebRTC does it. Each end sends a STUN packet to get the NAT statefullness going.

Granted, it requires transferring of ICE connection candidates out of band (via the horrors of SDP)