Establishing P2P TCP/UDP connections (NAT traversal)

Is there any way to establish true P2P communication through TCP or UDP without an intermediary server? I understand that this is quite doable if the two computers have only public IP addresses but if they are behind any sort of NAT router or on a private network it starts to get tricky.. in fact the more I look into it the more it seems plain not possible. I have discovered STUN, TURN and ICE protocols and hole-punching but as far as I understand they all require some sort of server to at least establish the connection. I am amazed something seemingly so simple seems so hard to do, am I missing something?
Ideally I am looking for solutions using Golang any help or examples in C++ would also be useful, thanks.

This is not strictly a Go question — it's a general networking question.

The reason this is so difficult is that the Internet was never designed to support NAT, NAT just happened and broke a lot of functionality. The clean solution to your problem is to switch to IPv6, where there is no NAT, but that might not be possible

If your NAT box supports NAT-PMP or uPNP, you could use that. The simplest way would be to create a cgo binding to libminiupnpc, or you could go fishing for a native Go library.

If your NAT doesn't support either of these protocols, then you're probably out of luck, as hole punching is a fragile and difficult technique that you will probably find difficult to implement.