Back in the 'early days' of the web, people hacked web servers using non-standard APIs in whatever language they had handy. Back then, the NCSA HTTPd was the defacto standard, so you mostly used C, I believe. Certainly, each HTTP server product had it's own C API (Netscape had NSAPI, Microsoft ISAPI, etc).
To alleviate this, in 1993 the CGI standard (Common Gateway Interface) standard was developed, allowing a web server to interface with a local process to handle requests. Because web servers were almost exclusively run on UNIX systems, the interface uses environment variables to communicate with the process, and each new request is handled by a new process.
Because you could now use any UNIX process to answer a HTTP request, you could use any language you liked for CGI programs. Personally, I started using shell scripts at first (simply emailing the contents of a web form) but quickly picked up Perl and the emerging CGI.pm module. Per request performance didn't much factor into things yet, the web wasn't so busy at the time. If you needed a fast response time you used static files or one of the aforementioned C APIs to directly interface with the HTTP server.
Java didn't enter the world of computing until 1995, and was first aimed at in-browser applets before becoming popular as a server-side language. By that time, dedicated web application servers, extension modules such as mod_perl and dedicated web programming languages such as PHP, ASP and ColdFusion started to appear. Each of these have had their following, some still survive today. None of them were ever dominant or clearly "first".