Howto: Recover your 2 Factor Authentication Secrets from Google Authenticator

By now most of you have probably already heard about 2 Factor Authentication and are probably using it for some websites, like Google. Also, chances are, if you are on Android device, you are using Google Authenticator app. The problem is: if you change your phones, wipe it, or loose it, you are left with a HUGE HEADACHE trying to recover your codes to re-generate tokens.
To preven that from happening, you have couple of choices: