It existed, but was definitely not in wide use. I worked for several early internet providers during that period (mid to late 90's.) Most folks had public addresses on their desktops. No customer we ever set up wanted NAT. Most didn't even have firewalls, sadly! Some of these were small companies, some of these were large corporations or universities.
And I'd argue NAT actually is necessary if you want IPv4 for home use. We'd be out of addresses otherwise.
ISPs didn't use it in the early days, but it was used in corporate/organizational networks. The PIX was apparently marketed as a security appliance (heh) so that defined the user base to a large extent.
You can access the web over v4 with other kind of proxies besides NAT, for example application level HTTP proxies.
If you want working v4 for all the protocols, NAT is out by definition anyways.
