Exhaustion was raised for 32-bit IPv4 in the very early 90s, when we had a few million active Internet users. Allocations were very sparsely used and growth in Internet usage was exponential. It didn't take much of an imagination to foresee a problem.
A 36-bit Internet would be little better. By the middle of the 90s we had ~45 million active Internet users, ending our 16x space advantage, even assuming we didn't just squander that with 8x as wasteful Class A allocations and bigger spaces reserved for uses that will never arise.
Today, we have ~70 billion connected devices: 5-6 billion home subscribers each with multiple devices in the home, 7.5 billion smartphones, 20 billion IoT devices, and all growing rapidly.
We'd need NAT. But NAT was a response to exhaustion concerns, as a stop-gap measure to provide time to design and transition to a proper solution. If we didn't have exhaustion concerns, there'd be no NAT. If we did have exhaustion concerns, brought on perhaps by the lack of NAT, we'd still have invented IPv6, because we'd still have been able to forecast that the Internet would rapidly outgrow 36 bits of address space.
edit: disclaimer, I work in this space, but my comments reflect my own opinion and are not necessarily those of my employer.
It's improbable that I'm off by an order of magnitude: 7 billion is far too low (we have 7.5 billion smartphones in the world!) and 700 billion is far too high; how low an estimate could we make without being unreasonably optimistic? 40b seems quite low to me - 7.5b smartphones, 5.6b connected users, 20b IoT devices, and commercial use of IPs - but if we took that value we'd be sitting at saturation for 36 bits of address space (60% utilisation is pretty darn good!) and the next decade would kind of suck.