All you need is a proper dynamic port opening scheme like NAT-PMP. You may also want to use a third-party STUN server to exchange routing info, but that's no more complex (actually easier) than DNS.
It's still the internet even though you need DNS to turn names into IP addresses, right? It's just a little more complicated. That's what the new world will be: the Internet, but a little more complicated. Which is exactly what happened when DNS, then CIDR, then NAT were introduced.
As important as DNS is for the Web, the Internet doesn't currently (and shouldn't) need DNS (or a DNS-like coordinator) any more than cupcakes need candles. If I know your telephone number, I shouldn't have to dial the operator and ask for their help (and implicit permission), I should be able to help myself and dial direct. We are re-imposing an unnecessary middle layer that has all sorts of social equality/neutrality implications. (People with global addresses have more power than those who don't.)
That's the point of direct addressing: removing ambiguity and allowing direct connections.
Edit: The cost of patching IPv4 is just another reason to move deliberately to IPv6 (or something that allows direct addressing again, but for the sake of argument, IPv6 is the leading candidate).
I think you may be misunderstanding NAT-PMP. Done correctly, that protocol can open a port through multiple layers of NAT without having to know how many layers there are. And then you'll have a well-defined public ip:port that other people can connect to you on. (You could, for example, advertise that ip:port in dynamic DNS or a bittorrent peer discovery protocol, just like you do today for dynamically-assigned IP addresses.)
There's no doubt that direct addressing is simpler and more appealing. Yes. But it requires worldwide 100% deployment of a replacement to IPv4, which is not simple at all.
There's still an upper limit of 64K listening ports at the top level of NAT for both TCP and UDP. The UDP side is probably worse. A shortage of UDP ports would pin down DNS servers to a single IP:port and make spoofing responses easier. You'd also need a DNS cache at each level of NAT to avoid burning through top-level UDP ports for DNS. That would mean that any successful DNS poisoning would hang around until the bad responses get flushed out of the resolvers. (If you're very lucky and the TTL is followed correctly, that would be after the top-level TTL expires.)
The cost of patching IPv4 and working around the quirks seems similar and less desirable to the cost of simply running IPv6 in parallel. I wouldn't describe it as all-or-nothing, but I would say ISPs need to help by providing low-latency tunnels/advertised routes. (Hurricane Electric can't handle everything, going forward.)
The problem isn't that it's expensive for ISPs to deploy ipv6; the problem is that an ipv6 address is strictly worse than an ipv4 address[1]. Therefore deploying ipv6 would be spending money to give customers something they don't want. Nobody is going to do that! 98%+ of customers will be happier with ipv4 behind CG NAT than an ipv6 address, as they don't see the internet as a network of peers, but rather see it as "I'm a client, I want to connect to servers"
[1] By "strictly worse" I mean there isn't, currently, any server that anybody cares about that you can connect to solely with ipv6; there are, however, numerous sites that are only connectable to with ipv4.
It's not really a case against IPv6 that existing websites don't need it since that's a privileged position that makes IPv4 seem fine. IPv4 exhaustion is only a problem for individuals at the edge who want incoming calls (to act as servers). Fortunately, today, new edge-homed servers can already use IPv6 through a tunnel, with the immediate advantage that they have a "real" globally-routable address that they can be reached at. In that sense, IPv6 has already arrived. It would just be nice if I didn't have to set up that extra tunnel to connect to something that only I and my clients connect to.
The people at the edge who don't care are, sadly, the one's who would most benefit. I agree that that is a problem. These social problems (the consumer apathy and the willingness of ISPs to exploit that to make a peer network a broadcast tree) are admittedly overwhelming but, as you also note, the costs to ISPs are minor: IPv6 can be provided to the edge, even if it's ultimately tunneled over IPv4-only hardware.
This is more a matter of technology-leaders, IMHO, pushing/expecting ISPs to do the right thing for once (if we can spare a few minutes from selling censorship to dictators). History has shown they aren't going to do it without public pressure. Their preferred distribution medium (cable TV) already existed: it was people who understood that it was a peer network that drove the adoption of the Internet. If IPv6 spends the first 10 years or more being used exclusively by that group of people, fine, but it's still worth promoting. ISPs only started taking it seriously in the last few years, so there's a long way to go, but I think it's a reasonable goal to get an upstream IPv6 router advertisement, eliminating the need for tunnels, to every IPv4-connected home in the next 5 years (it is really just a matter of installing Linux, or your preferred OS, on a spare box until the load dictates an upgrade; there is no chicken-or-egg problem).
there isn't, currently, any server that anybody cares about that you can connect to solely with ipv6
If a consumer-facing network with millions and millions of devices uses IPv6 exclusively for their management network to keep the service running effectively and efficiently, do I care? Do they?
It's still the internet even though you need DNS to turn names into IP addresses, right? It's just a little more complicated. That's what the new world will be: the Internet, but a little more complicated. Which is exactly what happened when DNS, then CIDR, then NAT were introduced.