I once lost a device with my Google Authenticator...Luckily, I had only 2 accounts on it. It was frustrating thou. So I decided to post this so that some newbies like me will not make the same mistake.
Write down BACKUP CODES!
Most sites provide you with backup codes when you create 2FA. These can be used once in case you do not have access to authenticator. Write them down and store in 2 physically different locations.
Double Device 2FA
You can also set up your 2FA on two devices whenever you enable 2FA or create a new account.
Write down the QR code
Click the "show code" or "can't read the QR code?" and get a text version that you can then write down. Dont forget to label the QR code or text code is (e.g. "2FA for KuCoin").
NOTE:
Keep your username, password, and 2FA phrase/QR code/recovery codes separate. If they are together, then it's no longer 2FA.
While writing your codes down, write it twice in case you overlook something. Write it down, and set up Google Authenticator from the key you wrote down (not the one on the screen), then verify via the code that displays on your phone. All to be on a safe side.
I have also experience this kind of scenario with my Kucoin account and I have not manage to retrieve it. I dont care about it anymore though. I dont have much in that account anyway. Lesson learned: DO NOT LOSE YOUR PHONE.