The real question isn't "Can you compete with Google" but rather "Should you compete with Google"?
Startups have slim chances of success to begin with. Making them even slimmer by battling it out with Google isn't a very good idea.
Why not just find another idea (or not start a company around something that one of the web giants is likely to go into soon enough in the first place).
I think its possible to compete with Google on most things, except Web Search. Google has web search nailed down. I think this is the reason when people give advice to startups they nearly always say: Find a niche, or do one thing really well... Google does Web Search better tahn anyone else. Can it be done better, of course.