Economically deleting data from app engine
Presuming your goal is to delete for the cheapest cost, rather than face migration, I would launch a self-scheduling task, that would clean up several hundred/thousand keys in each run, then re-schedules itself. I would purposefully throttle this task on a separate queue so that the task ran only often enough to avoid hitting my daily free quotas if possible.
If you have some "acceptable" CPU cost per day that you'd be willing to live with, you could throttle the queue less, either way it would be better if each delete doesn't take too long to complete so it doesn't impact instance latency too heavily.
kevpie's comment on vacuuming may also be relevant if you have composite indexes.
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.