Both are commonly used. If the number of results on a google search is a reliable result, it's no skin off my nose is slightly more common than it's no skin off my teeth. Personally, I prefer the nose version, because your nose has skin, but your teeth do not. In fact, the teeth version probably originated, like Alenanno suggest, by a mixture of idioms. The nose version is more canonical, that is, it is the original expression.
There are also other similar alternatives to the idiom:
It's no skin off my back
(and there are several others you can find easily in a google search that I will not mention here.)
You could use any other part of body and the meaning would probably still be understood. no skin off my elbow is very rare, but attested. If you wanted to be different than everybody else, you could say, it's no skin off my thumb web.