Have you actually tried using clojure? Last I heard, relying on a large jar like clojure meant you spent 29 of your request's 30 seconds loading the jar and had only 1 second to do real work before GAE killed you.
I'm looking at a live App Engine console for the Clojure app I'm working on right now, and I see cold-start JVM times varying from 3 to 10 seconds. Although this is a lot, with the latest App Engine, you can (1) pay $9/month to have 3 JVMs always running, and (2) your app receives warm-start requests which will cause a new JVM to start before it's needed.
In other words, your users should (almost?) never pay the penalty for a JVM cold-start. A single JVM stays around to serve requests as long as App Engine detects sufficient load to justify the resource usage.
The Deadline (https://the-deadline.appspot.com) is written in Clojure and runs on GAE. If this problem still persists, somehow they must have found a way to deal with it.
I gave up on Clojure running on App Engine a year ago because I could not get the loading request time below 3 seconds. It is not as bad what you describe, but it was a problem. The loading requests happened frequently enough that users noticed the lags.
