I remember losing cell service after a storm, but the internet still worked. I couldn't login to gmail (~10-12 years ago when this was the only 2fa) because my phone couldn't receive text messages with the 2fa code.
Even if you lose all the keys to your house, you'll need to get new locks. If the locksmith who is going to let you into your house does everything by the book, they'll need you to prove you actually live there. I had a friend thrown in jail for a day because his ID, keys, etc. were lost in a kayaking trip, and was arrested for attempting to break into his own house.
My point is, there really isn't a good answer here. The platform equivalent to hiding keys in the bushes is printing out one-time passwords. That works pretty well, but also has its own drawbacks.
1. Use a guid-like value as your internal identifier. All internal references in your databases to a user should use that.
2. Use a second user friendly identifier for the user to login (i.e. Email). Feel free to rebind this if the user needs to change it. Keep a 1-to-1 relationship between the two.