Google authenticator app Can't remember what it is called, but I used to have that google authentication code generator app on my phone which would be used to enter a special code for the 2 step google authentication system.

My phone has been damaged, so I have a new one now.  But I can't log into google because I don't have that authentication app install on my phone, and I can't install that authentication app on my phone because I need the authentication code...

What can I do?
Goto security tab of your Google account settings and disable 2-step verification.

Then install the authenticator app

Now you can re-enable 2 step verification which should work normally.