(A) Secret key. When a user is setting up 2FA for his/her account, the system generates a secret passphrase/QR Code as a crypto key, with instructions for user to write it down or print it out, then store it at a secure location.
(B) Manual review. The policy of a hosting company I use, is that when a 2FA-protected account is lost, the user must submit a national passport and proof of payment to reset the account manually.
And if user wants to add a new device.
(C) Send a challenge to the original device. If the system is in form of an app, it's as easy as showing up a Yes/No warning in the app: someone is adding a new device to your account, do you trust it? This is commonly used for various chat apps.
However, all the methods are not going to work for your use case, as the user wants to bypass the 2FA when setting up a new device... Currently, I don't see a satisfactory solution, otherwise, it effectively opens up a loophole and nullify the advantage of 2FA.
Let's see what other readers are saying.