Expensive, and good luck getting client trust back after what they did with App Engine.
No. There hasn't been for quite some time.
http://www.appscale.com/ provides hosting services on top of an open-source codebase you can (with some effort) deploy on your own.
GCE should be more flexible since it is providing infrastructure rather than the platform. However, depending on your project getting an entire platform from Google first could save you effort.
[1] http://code.google.com/p/googleappengine/issues/list?cursor=...
[2] https://developers.google.com/appengine/docs/python/tools/li...