Use non-blocking IO, like PyCurl.Multi interface (or any other Curl.Multi bindings). You'd have to generate DELETE cmmand URLs to call from some S3 library, the rest is up to Curl (to call those URL).
It's not a trivial task, but reasonably exprienced Python (or maybe even C) programmer would do it easily. (I'd say in a couple of days) And I can confirm that even on EC2 small instances 700 HTTP req's a sec is achievable (not sure about S3 API usage limiting).
the solution I used leveraged non-blocking I/O in a roundabout way. 150 separate procs (quick and dirty) per instance. no threads. I let the OS manage the I/O in that regard. My thinking was that if I had "a lot" of procs trying I/O... I'd get the same effect. again... quick/dirty.
It's not a trivial task, but reasonably exprienced Python (or maybe even C) programmer would do it easily. (I'd say in a couple of days) And I can confirm that even on EC2 small instances 700 HTTP req's a sec is achievable (not sure about S3 API usage limiting).