I was part of a team that deployed an e-commerce site that made international news in 1998, that used AJAX-type techniques in a way that worked in IE3 on Windows 3.11. (Though this was not part of the media fuss at the time; that was more about the fact of being able to pay for things online, still)
The arrival of XMLHTTPRequest made it possible to do everything with core technology, but it was already possible to do asynchronous work in JS by making use of a hidden frame.
You could direct that frame to load a document, the result of which would be only a <script> tag containing a JS variable definition, and the last thing that document would do is call a function in the parent frame to hand over its data. Bingo: asynchronous JS (that looked essentially exactly like JSON).
Since there were also various hacky ways in each browser to force a browser to reload page from cache (that we exhaustively tested), and you could do document.write(), it was possible to trigger a page to regenerate from asynchronous dynamic data in a data store in the parent frame, using a purely static page to contain it.
In this way we really radically cut down the server footprint needed for a national rollout, because our site was almost entirely static, and we were also able to secure with HTTPS all of the functions that actually exchanged customer data, without enduring the then 15-25% CPU overhead of SSL at either end (this is before Intel CPUs routinely had the instruction sets that sped up encryption). We also ended up with a site that was fast over a 33.6 modem.
This was a pretty novel idea at the time -- we were the only people doing it that we knew of -- but over the years I have found we were not the only team in the world effectively inventing this technique in parallel, a year or 18 months before XMLHTTPRequest was added to browsers.
(IE3 on Windows 3.11 was a good experience, by the way. Better behaved and more consistent than Netscape)
At around the same time we were also exploring things like using Java applets to maintain encrypted channels and taking advantage of the very limited ways one had to get data in and out of an applet. For example you couldn't push out from an applet to the page easily, but you could set up something that polled the applet and called the functions it wanted.
I don't like to get all "get off my lawn" but it feels like we actually earned our keep back then, getting technologies to do stuff that no standards working group anywhere was really considering and for which precious little documentation actually existed. There's a generation of us who held our copies of "Webmaster In A Nutshell" and "Java In A Nutshell" very close.