I would create the index on the columns in your delete statement's where clause.

It won't take that long if the disk is fairly fast and your delete will be far far faster.

If you have enterprise edition you can create the index with online=on.

If you do go that route, make sure to calculate the space the index will consume when you add it.