Tenho certeza de que, se eu disser "peer to peer", você encontrará instantaneamente uma solução!
Essencialmente, você está escrevendo um bate-papo P2P. O problema do NAT com redes P2P tem muitas soluções; para citar alguns:
Continue a sua pesquisa tendo em mente "Quero escrever um chat P2P" e encontrará muita documentação.