Marketing Cloud API Get Contacts Who Are Not in Any Channel

There's no way to query all contacts at the moment. You need to raise a support ticket to get an extract in a data extension. I described the reason and the way to proceed here.

With this base data extension you can use further queries to isolate the contacts that you want to delete.