However, until then, GCM [1] seems like a really good workaround. And I believe it is actually free of charge and available for both iOS and Android.
I think solid decentralized service discovery and direct routing would be as pivotal as the Blockchain itself. One actually helps solve the other, e.g using an altcoin for anti-spam. But the direct routing (a better NAT hole punch) apparently is not possible without service provider cooperation.
Tor is probably the biggest reliable semi-centralized overlay network, I'm not sure if there are any better options for punching through NAT that don't involve running your own public relay or trusting a 3rd party. But I assume Tor is much too slow to support realtime voice between an arbitrary client and hidden service?
Bitcoin miners faced a similar problem of needing to build a higher speed relay network to shuttle large blocks faster than the existing P2P relay network. In that case there was a group of P2P nodes configured to allow much larger number of peers combined with dedicated fast paths between themselves each located in high-speed hubs. I'm not sure if it was ever deployed.
If Comcast isn't applying an aggressive inbound firewall, pretty much noone will.