I have to get to work but here's a 60,000 ft view of what I would do...
1. DO A FULL BACKUP!!!!!!!!!!!!
2. MAKE SURE POINT-IN-TIME BACKUPS ARE BEING TAKEN111!
3. Create an empty identical table.
4. Do a cascaded-rename (takes about 63ms) to rename the old table to something else and rename the new table to what the old table was named. This new table will continue in the place of the old table.
5. Insert the desired old rows from the old table into the new table using a WHILE loop that does it in 3 million row batchs (most systems will reach a tipping point shortly after that so I wouldn't go much higher if at all).
6. When you're absolutely sure that everything worked correctly, DROP the old table.
--Jeff Moden
Change is inevitable... Change for the better is not.