The Torah prohibits, generally, the infliction of a wound on yourself or someone else. See Lev. 19:28. The obvious exception is the commandment to perform a bris millah (circumcision) on a male convert or eight-day-old Jewish male. But from where do we find a justification to pierce a girl's ear or nose? I know that, in Rivka, we have precedent for piercings, but how is that justified against the commandment?
The original question as well as @SAH challenge seem to imply that the Torah forbids piercings. This belief is possibly coming from the prohibition of tatoos as the prohibition to injure oneself. But as we will say the halacha doesn't necessarily consider all body piercings forbidden.
As context, plastic surgery (a more extreme form of bodily injury for beauty) is generally forbidden except when it serves to reduce pain or suffering coming from a bodily deformation. The reason is that the Torah prohibits wounding another person (Devarim 25:3) and the Gemara (end of Bava Kama 91a) states that this prohibition applies even to wounding oneself. The broader background is that the Torah doesn't consider a person's body to be his to do what he wants with it. It is an instrument in the service of God.
The Rambam writes that this prohibition applies when it is performed in a painful and degrading manner. R Moshe Feinstein (Choshen Mishpat 2:66) infers from the Rambam that if the wounding is done in a beneficial manner the prohibition of chavalah (to others or oneself) does not apply. An individual may wound himself if it is done for his benefit and with his consent. As such RMF allows plastic surgery for beautification to find a husband.
Addressing the same question of a girl performing cosmetic surgery to facilitate finding a husband, R Breisch allows it for another reason based on Tosfot (Shabbat 50b, sv Bishvil) allowing removing scabs from a body because of psychological pain (“If the only pain that he suffers is that he is embarrassed to walk among people then it is permissible, because there is no greater pain than this.”)
R Yitzchok Yaakov Weiss (an important posek in matters of medical halacha) agrees that the prohibition against wounding oneself is only relevant if it is done in a destructive or disrespectful manner (Minchat Yitzchak 6:105). Since body piercings do not involve physical dangers nor are they destructive or disrespectful, it would appear that this interdiction also doesn't apply.
The above provide the halachic justification for earrings.
Interestingly, the poskim who rule against cosmetic surgery (e.g., R Eliezer Waldenberg, the Tzitz Eliezer), do it on the basis of the danger involved and the interdiction to place oneself in danger. But perhaps even he would allow pierced ears as there are several opinions that say the prohibition of self wounding does not apply when there is no bleeding.
Body piercings are somewhat more complicated than earrings and depend on the reasons motivating the piercing. Doing it for beauty is allowed. Imitating the non-Jewish world is not because of the prohibition of hukot hagoyim (SA YD 178), and, depending of the piercing's erotic appeal, the commandment to be holy (Vayikra 19:2) and the notion of Tzelem Elokim (man being in the image of God).
PS. The fact that Rivka was possibly wearing a nose ring doesn't necessarily mean this is allowed or disallowed. The topic of our patriarchs observing all of Torah is not taken literally by many commentators and cannot be used to decide halacha.
PPS. The above is limited to women (as per the original question). The issue of men piercings is different since we men are forbidden to act in the way of women (SA YD 182:1 and 182:5), so it would be forbidden in a society where only women typically wear piercings, although there might be possible allowances if the wound is not permanent.
Read Igros Moshe Choshen Mishpat 2:65 and 66 who discusses elective surgery and difference between destructive wounds and unharmful wounds.The tshuvah is very lengthy and goes through the gemara,Tosfos and Rambam. At the end of the tshuvah he brings a gemara in Bechoros 45a which brings a case of a person who has an extra finger and then removes it, it is called a mum(deformity) and since the Mishna doesn't say "even though it is incorrect" it is a bit of a proof that in a case of beautification it is allowed. Same would apply to a woman that if it is for beautification it would be permissible. See the tshuva inside for the whole back and forth of the sugya. http://hebrewbooks.org/pdfpager.aspx?req=921&st=&pgnum=286&hilite=
HaRav Aviner responded to the question of girls getting their ears pierced as follows
It is negligible (Ha-Rav Aharon Lichtenstein – Rosh Yeshiva of Har Etzion, related that his daughter wanted to have her ears pierced, but he had doubts as to whether it is permissible. They agreed to go together to ask Ha-Rav Shlomo Zalman Auerbach, and follow his ruling. Ha-Rav Auerbach did not understand what Ha-Rav Lichtenstein wanted from him, and he said: "What is even your question? By us, boys have a Brit Milah and girls have their ears pierced!" Ve-Alehu Lo Yibol vol. 2, p. 172)
Several Mishnayoth and Gemaroth are linked to the question. Through these texts that we will discover the Halacha.
The first appears in Mishna (Baba Kama Chapter 8 Mishna 5)
"הַחוֹבֵל בְּעַצְמוֹ, אַף עַל פִּי שֶׁאֵינוֹ רַשַּׁאי, פָּטוּר"It concerns the right to wound itself.The Gemara's Pilpulim evoked in this connection:
- the damage,
- reversibility, following diverse verses. The choice of Rav Chisda who preferred not scratch themselves with thorns that tearing his clothes seems generally admitted, because the wounds are not definitive.
- The second
is found in Massecheth Maccot (Mishna 3, 5)
"וְהַשּׂוֹרֵט שְׂרִיטָה אַחַת עַל הַמֵּת, חַיָּב"It mentions the act of skinning own skin in a precise circumstance of bereavement, not linked to piercing.
- The third
(Macoth Mishna 3, 6)
"קִעֲקַע וְלֹא כָתַב"This concerns the injury foregoing dye in a tattoo. It is also in a particular context not linked with piercing. The case of Sreeta and Ktoveth KaaKaa (counted among the 613 Mitsvoth) appears to meet the conditions of 'utility' and are not damage (an allusion to issur Kollel), it is for this that takes place in 613.
- The fourth
(Macoth Mishna 3, 14)
"הוֹסִיף לוֹ עוֹד רְצוּעָה אַחַת וָמֵת"This is the act of physically repress someone without court approval.
- The fifth
If I could afford it, I mentioned cases or talking about piercing the ear.
In Mishna Bechorot (Chapter 6, Mishna 1)
"עַל אֵלּוּ מוּמִין שׁוֹחֲטִין אֶת הַבְּכוֹר, נִפְגְּמָה אָזְנוֹ מִן הַסְּחוּס, אֲבָל לֹא מִן הָעוֹר"It talks about the consequences of a perforation of the outer ear of an animal in the cartilage or or in soft tissues ('tenerus/tenerum' in Rashi Humash, Bartenura, is 'tender' in old French and Latin, 'tenero' in Italian up to day). The cosmetic defect "מום" is not relevant when the hole is on the soft tissues only. (Gemara 37B)
- The sixth
Succa (Chapter 3, Mishna 6)
"נִקַּב וְחָסַר כָּל שֶׁהוּא, פָּסוּל. ... ..., נִקַּב וְלֹא חָסַר כָּל שֶׁהוּא, כָּשֵׁר"This speaks of the beauty (and perhaps of health) of a cedrat when perforated. In Gemara, there extend the discussion about Tereyfoth. The piercing of soft organs that makes Tereyfoth is not relevant here
But if the piercing is considered as a way an embellishment (a way to ward off the body beautiful jewelry), the damage is not a damage and suffering is not in vain. It may be allowed for women. But this is not sufficient to prove that it is allowed.
What is piercing?
Piercing generally 1.- does not damage the cartilage and 2.- does not remove flesh, and 3.- the hole is not enlarged. 4.- It does not compromise the appearance of the body, since it does not result in default for the firstborn of cattle or the priests.
I'm not convinced that this is a specially intended 'instrument of sexually attract', but this leads to a feminine dress attitude. I do not think it's qualitatively different from a simple earring(unanimously accepted in women). It's a bit eccentric although in parts of the body. In our time it really not surprised people. I see no difference between piercing and any new feminine dress behavior. Piercing should not be prohibited for women.
 The subject here is not if it is a male or a female dressing habit.
Shemot 35:22 And they come in--the men with the women--every willing-hearted one--they have brought in nose-ring, and ear-ring, and seal-ring, and necklace, all golden goods, even every one who hath waved a wave-offering of gold to Jehovah.
As you can see, the nose and ear rings were donated to build the Mishkan. This is how one can conclude that ear and nose rings were an acceptable offering for the most holy place. Just like they would not donate pig's skins for the Mishkan, so if nose or ear rings were abominable they would not be permitted as a terumah for the Mishkan.
See also Bemidbar 31:50 where ear rings were acceptable for atonement.
In fact, I think it is very poetic. Women donated their most precious adornments for the Mishkan, which shows how willing they were to build it, so God may dwell among them.