As a postgrad student, is it appropriate not to add my supervisor's name on publication? Let me summarize the complicated state of affairs, as follows:

This summer, I was cooperating with the other team in a spin off project, we decided to publish the results, so I prepared the paper. 

In the authorship, I added my supervisor's name. I think it is usual because I am his student and whatever I've learned came from him.

But when the other team's supervisor saw this, he asked me to drop my supervisor's name from the list. I sense that this is not only because he is not involved in the project, but also because of some political issues. 

Dropping my supervisor's name makes me feel bad, like betraying him.
Since you haven't explicitly mentioned which academic discipline this concerns, and as EnergyNumbers mentioned in the comment, different disciplines may have different conventions, I'll answer in terms of my discipline, (Theoretical) Physics. I would be horrified if it so turns out that things are any different in any other scientific discipline (at least). 

Whenever an article gets submitted for publication, one has to''accept'' a declaration that all those people who made significant contributions were (at least) offered co-authorship. If they decline to be an author, that's a different story. As PVAL mentioned above in a comment, it is academic dishonesty if someone is sitting in the author list without having contributed anything significant to the investigation. Even if you discount the ''politics'', as you mentioned, the other team is frowning because your supervisor is ''not involved in the project''. If that means that he only offered occasional advice, perhaps born out of his experience with doing similar things, (''have you tried ...'' variety), then the right place for him is in the acknowledgements section. Just mention, ''we thank [his name] for helpful discussion/ inputs ...'' etc. But if it means that you want to include his name only because ''what I learned came from him'', I'm afraid I have to point out that authorship is not a Christmas card. (By the same token, why not include your parents, or your spouse, or your high school teachers - you owe a lot to them also :P). It is WRONG to include any person who didn't contribute TO THE INVESTIGATION, howsoever highly regarded he may be in your personal life.

But having said that, here's some seasoned advice - Go and talk to your supervisor in private and explain the situation. Ask him whether or not you should include him in the list, fighting opposition from the other co-authors. It is possible that he may have been in this situation before (whichever side), so he will show you the light. One-to-one dialogues go a long way in resolving these sort of harmless dilemmas.

Besides, that will serve another purpose - you will show him that you ''respect'' him so much that you want to gift him authorship in an investigation that he hasn't contributed to at all :P. (I expect that any sensible man would decline in this situation).