I recently traveled for 6 months without a data connection on my phone and used the Google Authenticator app without any problems at all. I changed the timezone setting many times too.