Did you print out the recovery codes when you setup 2 Step? That it states very clearly to do in case you ever loose your phone?
Otherwise you are SOL, you maybe able to contact google, ( But that's a fun task ) and see if they can authenticate you and release the 2 step.