~
I understand the pain.
I found this article on the web... hope it will help.Step 1: First you'll want to install and sign in to the app on your new device.
Step 2: Next, head to Google's two-step verification Web page using a browser on your computer. You may need to log in to your Google account to access the security settings.
.
.
.
.
Keep reading on the website.
I do hope it works for you.Let me know if it helps...
If you don't have any backup keys, I'm sure you can always contact their support and tell them your situation.
If it's with one and two websites then it's easier to contact and resolve, I really hope he did not use it for so many websites.
Updated after TryNinja's post.