First ,I will suggest you should keep QR code or key in the form of offline mode like you can have print out or you keep it in your mail.this is best way,if you lost your mobile,then you can recover from that.
But if you don't have and you have lost your phone.For this I have experienced this situation.
I have this experience with BITFINEX exchange,I mailed the support team for this .Then they mailed me and ask me to send a selfie/pic with having a identity card.Then, I mailed the selfie or pic with ID card.After 30 min. they removed my 2fa from account.I restored my account.
Do it,it will work definitely..
Good luck..