You can run App Engine apps on top of appscale which in turn does run on Eucalyptus, Xen, and other clustering solutions you can deploy on Ubuntu (not sure about there being any Windows support) -- looks like it may require substantial system installation, configuration, and administration work to get started (sorry, no first-hand experience yet), but once you've done that investment it appears it may be smoother going forwards. (Automation of task queues is a relatively recent addition to appscale, but it's apparently working and can be patched in from a bazaar branch until it gets fully integrated into the trunk of the appscale project).
Edit: since there seems to be some confusion about licensing of this code, I'll point out that the App Engine SDK, as per its site, is under Apache License 2.0, and appscale's under the New BSD License. Both are extremely permissive and liberal open-source licenses that basically allow you all sorts of reuses, remixes, mashups, redistributions, etc, etc.
Edit: Nick also suggests mentioning TwistedAE, another effort to build an open source way (also Apache License 2.0) to deploy App Engine apps on your own infrastructure; I have no direct experience with it, and it IS still pre-alpha, but it does seem very promising and well worth keeping an eye on (tx Nick!).