You don't need to reinvent TCP. You can simply put TCP over UDP. Works like magic :)
TCP hole punching works just fine in practice, but it's certainly a part of the "long tail" of empirical hacks that allow bumping NAT traversal rates into 95+% range. Detecting NATs that decrement ports is another. Ports that are incremented/decremented by more than 1 is yet another. And there's also UPnP that gives you another percent or so.
I was doing this as a part of the Hamachi project [0], almost 10 years ago, and this long tail was absolutely instrumental to being able to serve hundreds of thousands of clients off just few measly Dell servers for $300/mo in hosting costs.