For those services that allow you to use an app such as Google authenticator, there is usually an option to enter the displayed alphanumeric code manually rather than scanning the QR code. If you make a record of this code and store it securely you can enrol a new device using that code.
I've been caught out with the phone change issue before when I've forgotten to temporarily disable 2fa before wiping the old phone, and have tested the manual enrolment process for Google authenticator and it has so far worked well. I've stored the manual recovery code in my password vault (I know there are pros and cons to this, it's worth considering the risk of this before you follow my practice).
Some services also publish recovery codes (Google does, and GitHub for example) and it is worth recording these securely as well just in case there is a 2fa issue.
Finally, some services (including Google and MicroSoft 365) permit the use of a texted SMS OTP if there is an issue with using 2fa, and it is worth recording your phone number with these services where possible (there is a risk of SIM cloning or unauthorised replacement of course, but this is probably smaller than the likelihood of loosing access to the 2fa tokens - your mileage may vary so consider your own likely risks either way).
Like any authentication management process, the use of 2fa needs planning at the time of enrolment: what recovery options are available, what is my process for decommissioning a lost/deleted/compromised authentication token (including access to any app)? Keep a separate register of services and recovery options and prepare for the worst!
It's too late after losing an authentication token - the way back to a normal login process is often very painful and slow.