What evan_ said: you're using the phone as a pocket computer, not as a phone. You don't need phone service at all--the authentication program will run on your phone even if you don't have service or you're in a foreign country.

Enough people have asked these (very reasonable) questions that maybe I should do a video about two-factor authentication.