Economically deleting data from app engine
Removing indexes first will substantially reduce the cost of deleting records. You could also limit your deletion rate to keep under the 6.5 CPU hours per day you're allocated for free, to avoid paying.
Regarding doing the deletion yourself, it's unlikely you can do it more efficiently than the datastore admin tool, which already does keys-only queries and uses cursors.
I have a popular social game, for which I was storing every user action as an Event entity in the data store and then once per day exporting these events from GAE for processing. Now I'd like to delete all of these entities from the data store, all 300 million of them.
I started using the "datastore admin" for this. In the first few hours I let it run, it managed to delete about 2 million entities and use $10 of CPU to do this. So it seems it will cost $1500 just to run this delete. I'm starting to think I would be better off just deleting the whole application and copy items I don't want to delete over to the new application. 
Any other options?
Update
I got advice on #appengine in IRC that simply getting the keys of 2000 entities at a time and spawning tasks to delete them in pieces (can pass keys as strings to tasks) may be cheaper than using the Datastore Admin tool. I am trying this now and will try to remember to report back tomorrow if this seems to be cheaper or not.