in a world where people tunnel everything of HTTP, and use thing like PPPoE, the overhead of a few more bytes in the header of each packet would not bring things to a screaming halt.
you could have left the existing 32 bits of addressing where they are in the packet header and set an option flag to enable additional addressing bytes later in the header.
If you did something like this, the 32 bit addresses would route you to the ISP that handles the 'full' address, and that ISP could have a router that implemented NAT by just grabbing the bottom 24 bits of the expanded address space and using the 10/8 network with these addresses internally (or a different class A could have been allocated for this purpose)
this would have allowed the address space to be transparently extended from 32 bits to 56 bits without any existing routers needing to be changed at all (including home routers), the client endpoints would need new software to send the extended headers, and the ISPs that run out of addresses would have to have new routers to move the bits from one point in the headers to the other (which is a _very_ cheap thing to do, much cheaper than current NAT where the router needs to maintain a table of translations, time them out, etc).
systems with the new 'extended' IP addresses would have trouble initiating connections outside their ISP to endpoints that did not include these additional headers in their response packets, but all that would take is 'if you see this flag and extra info in the headers of a packet that comes to you, include them in the response', and that's a pretty simple thing for the OS vendors to do.
I'm not worried about network vendors doing this for the network gear, as that should not have to be maintained across ISPs