I have worked at both Google and Facebook without any degree or certification. In my experience, these companies care a lot more about interview performance than formal credentials.
I was hired pretty quickly and easily with no degree. A degree from a prestigious four year college certainly doesn't hurt, but it's definitely not a requirement.