Breaking it into pieces and making sure that the delete statements are using indexes instead of scanning, those are really your choices if you can't partition the data.
"The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood"
- Theodore Roosevelt
Author of:
SQL Server Execution Plans
SQL Server Query Performance Tuning