The bar code was actually just a code to initialize the code generation (I think it is based on that randomly generated seed and the time, so that then server and client generate the same keys). You could have also typed in the code by hand.

How do you get 2-factor auth enabled at all without entering a phone number? Their help page says that you can switch from phone-based to Google-Authenticator-based authentication after enabling 2fa, but I can't find a way to skip the phone step for turning it on in the first place. This is the screen I get when I click to enable: http://i.imgur.com/cm6Km.png

Iirc, even facebook nowadays (at least in India) requires you to complete SMS verification during account creation.

Note that even a cheap, pay-as-you-go phone emits a breadcrumb trail of mobile network (and possibly GPS) location information. Unless you power it down between connection attempts. In which case it still emits breadcrumbs, though fewer.