You would have used Perl or PHP - I was using both from early 1996, and they worked just fine. Yes, they hadn't "matured", but they were functional well before Java or ASP were even available. Server-side Java was not something as widely available as Perl or PHP, and Java as a language was not written for the web like PHP was (easily embeddable in HTML, straightforward DB access, etc).

WebObjects - didn't have any direct experience with that back then, but it and many other proprietary options were quite pricey, IIRC.