First of all, I'd like to say that you should not view Google as the end all be all of software companies. I was also very interested in interning there, but was a bit dissapointed when I finally managed to get an offer.

How I did it:

I applied to about 30 big software companies in my freshman year. Obviously, nobody outside the country responded, but I managed to get an internship at Adobe Romania, which was a really useful and pleasant experience.

Once you have an internship under your belt, it's a lot easier to get interviews and offers, and also gives you something to talk about in your interviews. So, in my second year I interviewed with Jane Street, Google and Microsoft, and got offers from Google and Microsoft. Google offered me a position in web development, and Microsoft offered me a position in the Operating Systems team, so I chose Microsoft.

My advice would be to find an internship at a company where there isn't so much competition and use your experience to get an internship at Google next year.

Send me an email if you have any questions.