¿Debe almacenarse una clave de recuperación 2FA junto con una contraseña?

Para su aplicación, sugeriría, almacenar las claves de recuperación en papel normal que ponga dentro de una caja fuerte de la casa. Eso es suficiente seguridad. Prefieren robarte el token del teléfono o 2FA si realmente quieren tu cuenta. Y los ataques físicos son muy raros. En realidad, ni siquiera es necesario ponerlos en una caja fuerte. Puedes ponerlos en el cajón del escritorio en casa.

Pero no los almacene dentro del administrador de contraseñas, ya que existe un riesgo demasiado alto de que un troyano comprometa los códigos. Una vez que haya desbloqueado el administrador de contraseñas con la contraseña maestra, cualquier troyano puede comprometer cualquier contraseña en su administrador de contraseñas.

Puede almacenarlos en una base de datos de Keepass (con una buena contraseña). Puede imprimirlos en papel y guardarlos en un lugar seguro.

Puedes crear una máquina virtual de Android en Virtualbox, instalar Authenticator y usarlo como respaldo para 2FA. En Amazon AWS puede usar varias de estas cuentas, pero no sé si Google lo permite. Esa máquina virtual debe mantenerse en un volumen cifrado como Truecrypt o DMG, preferiblemente en otra máquina. Puede hacer una copia de seguridad en un disco externo y usar Virtualbox portátil para ejecutarlo (en un host de Windows).