Delete from table in chunks
The openark kit by Shlomi Noach could be right up your alley!

From the introduction here:


oak-chunk-update: perform long, non-blocking UPDATE/DELETE operation in auto managed small chunks.


From the documentation page here:


  This utility allows for splitting long running or non-indexed
  UPDATE/DELETE oprations, optionally multi-table ones. Long running
  updating queries are often used. Some examples:

Purging old table records (e.g. purging old logs).
Updating a column on a table scale.
Deleting or updating a small number of rows, but with a non-indexed search condition.
Inserting into one table aggregated values from other tables.



The tool has a load of options with examples - I was very impressed when I used a couple of his tools for various bits and pieces.

So, kick it off with cron at 03:00 in the morning and relax!