App Engine is a Platform-as-a-Service. It means that you simply deploy your code, and the platform does everything else for you. For example, if your app becomes very successful, App Engine will automatically create more instances to handle the increased volume.
Read more about App Engine
Compute Engine is an Infrastructure-as-a-Service. You have to create and configure your own virtual machine instances. It gives you more flexibility and generally costs much less than App Engine. The drawback is that you have to manage your app and virtual machines yourself.
Read more about Compute Engine
You can mix both App Engine and Compute Engine, if necessary. They both work well with the other parts of the Google Cloud Platform.
EDIT (May 2016):
One more important distinction: projects running on App Engine can scale down to zero instances if no requests are coming in. This is extremely useful at the development stage as you can go for weeks without going over the generous free quota of instance-hours. Flexible runtime (i.e. "managed VMs") require at least one instance to run constantly.
EDIT (April 2017):
Cloud Functions (currently in beta) is the next level up from App Engine in terms of abstraction - no instances! It allows developers to deploy bite-size pieces of code that execute in response to different events, which may include HTTP requests, changes in Cloud Storage, etc.
The biggest difference with App Engine is that functions are priced per 100 milliseconds, while App Engine's instances shut down only after 15 minutes of inactivity. Another advantage is that Cloud Functions execute immediately, while a call to App Engine may require a new instance - and cold-starting a new instance may take a few seconds or longer (depending on runtime and your code).
This makes Cloud Functions ideal for (a) rare calls - no need to keep an instance live just in case something happens, (b) rapidly changing loads where instances are often spinning and shutting down, and possibly more use cases.
Read more about Cloud Functions
Best Answer
You can have a look at AppScale
Its an open-source implementation of AppEngine which you can deploy on your own machines, with a host of databases to choose from.