What I can say, generally, is that you should not have a single point of failure. Be it your mobile phone (can be lost, damaged, stolen), some other computer or device (can be damaged), a piece of paper (can be lost, damaged) or even your memory (can forget things, especially if not used too often).
Just like passwords usually have fallbacks for recovery (ex.: having a password reset link sent to an alternate e-mail address), your 2nd factor authentication should also do the same, and if there's nothing built-in you'll have to make your own. Easier said than done, true, since every additional "step" solves one problem but introduces a new one (ex.: if I forget my e-mail password, I can reset it using an alternate one, but now I also need a fallback for my alternate e-mail password).
Your problem, IMHO, is that you created a "closed loop" in your fallback strategy: to access your e-mail you need your password manager, and to recover access to your password manager you need your e-mail. When planning the recovery of LastPass, you can't count on things that are dependent on having access to LastPass...
I don't think there's a one-size-fits-all solution to mitigate this problem, and all your suggestions are valid ones depending on the circumstances. Personally, here's how I protect my GMail account (I don't use password managers yet, so the e-mail password is commited to my memory):
- My personal (desktop) computer is marked as "trusted", so it doesn't require codes and only asks for my password once in a while (each 30 days, I think);
- My Android device has Google Authenticator, but to open it (or to open the GMail app itself, for that matter - or the whole 2-factor thing would be pretty pointless...) I need to provide a PIN for an App Blocker (so even if someone gains access to my phone he can't read my e-mail).
- There's an alternate phone number registered, so an SMS can be sent to it if I can't use mine.
That protects me from most "catastrophic" scenarios:
- If I forget my password and my phone is lost at the same time, I can still access GMail from my desktop (recovering administrative access is a bit trickier).
- If I forget my password and my desktop is broken at the same time, I can still access GMail from my phone (assuming I can still remember the PIN - something I use often).
- If my desktop is broken and my phone lost at the same time, I can still use my password and the SMS to the alternate phone to access GMail from another machine.
While retaining the 2-factor property at all levels:
- To access my desktop, I need physical access to it and my login credentials;
- To access my phone, I need physical access to it and my PIN;
- To access my e-mail from somewhere else, I need physical access to a phone (either primary or alternate) and my password.
(Note: strictly speaking, only physical access is required in the first two cases, if a skillful and silent/quick attacker is involved, but that's beyond the scope of this answer)