Yes, nodes behind NAT must be able to already communicate through some kind of intermediary — at least initially (for STUN), but maybe the whole time (for TURN.)
But this intermediary has very low requirements. It doesn't need to be mutually trusted by both parties, and it doesn't need any compute of its own for handling encryption/etc, just the ability to re-wrap opaque IP-packet payloads back and forth between ports. Any random low-power network switch could implement full-speed TURN. And anyone could also run a STUN or TURN server on a $2/mo VPS.
And, beyond that, STUN/TURN servers also don't need to be protocol-specific; you can reuse a STUN/TURN server someone put up to help some other protocol. They're a global resource — even STUN/TURN servers established for non-WebRTC routing, can be reused for WebRTC routing, and vice-versa.
This means that in-browser WebRTC protocols that rely on ICE, are both:
• affordable to "enable" connectivity on (because any network or protocol likely has some backing foundation, which can easily afford enough ultra-cheap STUN/TURN nodes to ensure the network's operation; but even if they don't, the network can be designed to use existing STUN/TURN nodes established by p2p advocates like the EFF, acting as a free rider on those nodes; and even if you don't do that, either party, with at least $2 of motivation to communicate, can get a VPS [in a non-CGNATed country] and run their own STUN/TURN nodes on it.)
• uncensorable in the weak sense (in that there's no central entity within the p2p network which can choose to deny you access to connectivity on the network.)
(Mind you, your ISP might drop all your STUN/TURN -looking traffic; or you might not be able to acquire a non-CGNATed VPS IP address anywhere in your whole country... but this is not a problem for "p2p protocols" to solve; as, at that point, you're not on "the Internet" per se, but on a weird LAN that is willing to route IP packets to some whitelisted subset of the Internet. Solving for network-level censorship isn't the domain of "p2p protocols", but rather the domain of anti-censorship technologies, like Tor's hidden bridge nodes.)
---
But I assume you don't really care about the practicality here, and are speaking more in the context of being an IPv6 public-routability maximalist. (Which, hey, I'm one of those too. Non-globally-routable addresses are silly.) Thus this:
> You can build such a thing with WebRTC, but only if the nodes are not browser hosted and have public IPs. If you think that's useful then you're also confused.
I do get why you say this — the naive counterargument is that phones on cellular networks are non-browser-hosted and have public IPs, and that therefore native mobile apps can act as both WebRTC and STUN/TURN servers.
But of course, the cellular networks that aren't CGNATed, are all IPv6 networks. So this is no help to anyone whose ISP has only assigned them an IPv4 address behind a NAT.
But there's an (IMHO much better) rebuttal, in the form of an emerging technology-trend, which you may not have considered: Desktop-as-a-Service (DaaS) nodes.
If you run a browser on a cloud VM, then you get a browser with a public-routable IPv4 address, where that browser can then participate in a WebRTC network as a "supernode."
Sure, if you're doing this with the goal of enabling STUN/TURN, then this is silly: you may as well just get the $2 VPS and run just the STUN/TURN servers on it.
But my point is that many corporate employees just connect to some DaaS using thin-client hardware by default, and do everything on that DaaS (incl. using a browser); and so, as long as your protocol is likely to be used by any corporate workers, then your protocol does get its necessary supernodes — in the form of the browsers running on these workers' VMs — "for free."