Authentication apps like Google Authenticator or Authy work without any data service of any kind. Most services provide backup codes you can print out and keep in your wallet or another safe spot in case you lose or destroy your device.
You can print two copies of your backup codes, keep one in your wallet and one at home. You don't have to worry too much about them getting stolen because they are useless without your password. You can also generate a new set of backup codes at any time, which invalidates the old ones.