Почитайте в сторону STUN в этом случае. Нужен пир с белым адресом, который выполняет для такого соединения работу организатора. В противном случае - никак.
Насчет сокетов - нет, самое то. И именно с этой целью просят для сервера белый IP-адрес, если не дают, можно просить организовать проброс порта через NAT с какого-либо адреса (скажем, запрос на 1.2.3.4:9999 на роутере 1.2.3.4 передается на 172.16.3.4:12345, где уже стоит сервер и слушает порт).