This is not an option because there is anothe batch process which keeps adding to this table new records continuously.

I am looking for an option where million+ rows can be removed seamlessly parallel to new inserts into the table.

There is no option of shutting down the inserts, running the deletes and re-starting the inserts.