Both are fine to use however they both have different meanings. As for commonality, it completely depends on the situation and where you live. I don't hear either one that frequently.
No Skin off My Nose is the equivalent of "I don't care, doesn't bother me". It can also be used passively aggressively (trust me on this one) or nonchalantly.
Skin of My Teeth commonly refers to barely managing to do something or to marginally (and seemingly impossibly) accomplish something i.e. escaping from something. It usually used in a hyperbolic fashion.
In NYC it isn't used very often except by the older generations (think born in the 30s - 60s)
According to wikipedia (and a few other sites I found but this one is easier to site) the phrase "Skin of my teeth" is the older meaning coming from the Book of Job from the Christian Holy Bible.
I am not finding a concrete source of where the phrase "Skin of my nose" comes from but I did find this site that, while doesn't cite (see what I did there), has an explanation that is amusing and a little alarming.
In sixteenth century England a clandestine group of cabbage worshipers inhabited London's seamier neighborhoods, practicing a variety of bizarre rituals involving cabbage—including coleslaw, sauerkraut, and the newly invented Reuben sandwich, which had been banned by the government as being subversive ever since the visiting Count Halitosis had disgraced himself by splattering corned beef on the tablecloth at a state banquet.
With informers everywhere, it became common among the cabbage cult to cut a very small hole in the doors of the places of worship, so that the high priest could peer through and verify the identity of those wishing to enter. However, electric lights being unknown, it was difficult to make out the faces of people standing outside in the dark, so another method was devised.
Followers who desired entrance to the service were to make a small mark, like a birthmark, on the left side of their nose, and then thrust their proboscis through the hole in the door. If the mark was missing, the priest would know that the nose did not belong to a true believer, and he would take a sharp paring knife and slice a long strip of skin from the nose. Understandably, the King's guardsmen came to be very wary of taking an assignment which could result in "skin off my nose", and eventually the phrase came to mean anything costly or painful. Those who had suffered the indignity of having their noses pared like an apple were, of course, subsequently easy to spot walking down the street, and peasants would tease them about the wisdom of "sticking their noses where they didn't belong".
Eventually the secret of the mark on the nose was discovered by spies who managed to infiltrate the cult, but the King, in his Divine Wisdom, refused to permit his guardsmen to stoop to such silliness, and proclaimed that any of his men wishing to keep their heads attached to their shoulders would do well to "keep their noses clean".
By Michael Dunkerton.