Обход NAT вполне реален в нынешних реалях?
Для «пробива» NAT существуют распространённые и широко применяемые практики, задокументированные в RFC5128, а также менее распространённые, но технические еще более продвинутые, вроде pwnat.

Слыхал об hole punching/STUN, но вроде для них нужен промежуточный сервер, но тогда смысл от децентрализации.
Промежуточный сервер в Hole Punching нужен только для согласования IP-адресов и портов. Если же IP-адрес и порт заранее известны (например, вы настраиваете UDP VPN между двумя пирами), то промежуточный сервер не нужен: просто отправляйте пакеты по UDP со статичными портами на обеих сторонах друг к другу.

Промежуточным сервером также может быть другой пир, а не обязательно централизованный сервер. В расширении ut_holepunch протокола BitTorrent DHT один пир может отослать другому пиру сообщение о необходимости подключения друг к другу путём отправки сообщения в DHT.
Очередной построитель "суперзащищенной децентрализованной сети", да? Олиферов сначала прочитай, сил нет уже такой бред комментировать. 

NAT обойти невозможно. В смысле, если нет ни одного сервера с белым адресом - то построение такой сети невозможно. Если же он есть - сеть всегда строится на базе коннекта к нему. 
Именно поэтому TeamViewer напирмер имел огромную кучу адресов, надерганных из разных блоков - чтобы сложнее было найти и забанить.