Would the S3 inventory help here? That would allow you to get the list of all files (albeit on a delay similar to the lifecycle rule approach), which you could process offline to generate the DELETEs.
S3 inventory would cost $0.0025 per million objects listed [1], while LIST requests are $0.005 per thousand requests and each LIST request can return up to 1000 objects, making them $0.005 per million objects listed. For the "Infrequent Access" storage tier, LISTs cost double that.
So S3 inventory would be half price compared to LIST (or quarter price in IA storage class), but that's still small comfort if you're staring down the barrel of a bucket containing a large number of objects.
What a confusing mess. If LIST pricing is separate then it's strange to include it in the column of a table of storage-class pricing like that. But I agree that's what that statement seems to be saying.
Either way, the takeaway is that using LIST or a bucket inventory, will still be O(N) cost and there's only a factor-of-2-ish difference between the two.
Then again, a billion objects is $5 territory to delete, and if you have a trillion objects to delete and no pre-existing listing to go off of, then odds are you can stomach the $5000 hit more easily than you could stomach the staff time spent trying to reduce that cost!
So S3 inventory would be half price compared to LIST (or quarter price in IA storage class), but that's still small comfort if you're staring down the barrel of a bucket containing a large number of objects.
[1] Management & analytics tab on https://aws.amazon.com/s3/pricing/