You still don't understand the issue. This is not about your technical skills, it is about your integrity. Integrity is considered extremely important in American society. Claiming to have a degree that you do not have is a serious lie, and calls your integrity into question. In American eyes, if you lied about that, you could lie or act unethically in many other circumstances. For a company like Google, that is a big risk, since they probably have a lot of secret information and access privileges that their employees are entrusted with.

Now, I am not saying that they are right about you. It is likely that your home culture is less strict about these matters than American culture, and while you would lie about the degree, you would not lie or act unethically in any circumstances that would actually concern the company. But how do you prove it to them? Your interview performance and job history do not prove it - they have to do with technical skill, not with ethics. You have only been at your job for a couple of weeks, so your boss and coworkers cannot vouch for your personal character.

I know you feel really disappointed right now. It sucks that this happened, and I know that it seems absurd to you. But you are going to rebound quickly and find other opportunities. What's important is that you learn something from the experience.