There was a third option: make the existing IPv4 space a hierarchically routed island of the new IPv4.1 space, with backwards compatible packet format, then upgrade just the endpoints in the first phase.
So every owner of a ipv4 would get, say, an entire 32 bit space that routes over existing IPv4 infrastructure. So, if the endpoints are upgraded, you have guaranteed end-to-end deliverability without silly hacks such as NAT or STUN.
This doesn't solve the "backwards compatibility" problem itself, because you still have two logical different IP networks running on top of each other, requiring separate name resolution, etc. But what it does solve is the "incentive problem": endpoints are incentivized to upgrade because it gives them an immediate benefit, end-to-end connectivity to other upgraded users with non-routable addresses sitting behind a dumb, non-upgraded IPv4 routers.
For example, VoIP or P2P software would immediately benefit and it would drive adoption for an immediate use-case. In the later stage, when the entire infrastructure can understand the extended packet format, you would start to publish extended routes that don't fall into the hierarchical range, similar to IPv6 today.
IPv6 lacks any such incentive, because me upgrading and enabling it has zero benefits until all hops separating me from the internet also enable it and correctly configure it. On the contrary, by requiring a completely new, complex configuration with no "default, just works" mode, IPv6 introduces a disincentive, because by enabling it not only do I not gain anything, but I risk breaking my internet due to misconfigured upstream. So the conservative setting for IpV6 has, for the last 3 decades, remained "off". This only recently began to change.