Google’s Two Step Verification is a great way to ensure your Google account is well protected. Â If you only have one Android phone/device stop – you need to go no farther, just follow the instructions on your Google account here. Â But how do you use it with two Android phones/devices?
If you’re like me, you’ve found that when one phone is setup the other fails to authenticate and vice versa.  To get them to both to work, I went through the process of setting up one as a new device here.  Now here is the trick, when asked to scan the QR Code, have BOTH phones/devices ready to scan.  Scan them at the same time before proceeding.  Now when asked for the verification code, just pick one code from either phone (odds are they will be different at the start).  Now they will be synchronized and will authenticate without problem.  I found that if both were running the Google Authenticator App, eventually they would show the same codes (but displayed at different times).
My guess is/was by scanning them individually (and not at the same time), each phone’s secret keys are different and thus were generating asynchronous codes. Which is why only the last setup phone would work and not the other.
Hope this works for you like it did for me. Â Enjoy!