If you are syncing with iCloud, you can go to icloud.com on a computer. Open the Contacts app on the site. Using the gear icon at the bottom; select all, then Delete.
Though you might want to select all, then export first, just in case it turns out there was something you didn't want to delete after all.