This was discussed just recently.

http://www.sqlservercentral.com/Forums/Topic1511574-3412-1.aspx#bm1511578

If you are deleting more than you are keeping you can populate a duplicate empty table with the rows you want to keep, delete the old table, rename the new table.

I know you said you can't use truncate, but you may wish to reconsider your reasons for not using it when it is the absolute fastest option available. You could populate a temp table with the rows you want to keep, truncate the table, then move the saved transactions from the temp table back to the original table.