Django as a cgi does sound painful, but that's because it's huge. Most cgi scripts I've written are quite simple. And they rarely have to serve 100s of requests per second. And of course it's possible to optimize the startup time, e.g. by dumping an already-initialized version of the script (even django). Emacs has done that forever. It wouldn't surprise me if there is some way to do it in Python.

I remember reading somewhere that amazon.com was originally implemented as CGI's written in C. And, Perl cgi scripts served the whole web for many years, on servers much slower than what we have now.