Is it possible to use 2-step verification with multiple accounts on a phone?
Yes, the Android as well as Blackberry versions of Google's Authenticator app supports multiple accounts.

Press MENU and choose SCAN BARCODE after you've set up your new Google Account for 2-factor auth to grab the displayed barcode or enter details manually.

Details: https://code.google.com/p/google-authenticator/