Melisandre uses rubies to put glamours on people and change their faces:
Rattleshirt sat scratching at the manacle on his wrist with a cracked
yellow fingernail. Brown stubble covered his sunken cheeks and
receding chin, and strands of dirty hair hung across his eyes. "Here
he comes," he said when he saw Jon, "the brave boy who slew Mance
Rayder when he was caged and bound." The big square-cut gem that
adorned his iron cuff glimmered redly. "Do you like my ruby, Snow? A
token o' love from Lady Red."
A Dance With Dragons, Jon IV
(note this is actually Mance speaking above, glamoured into looking like Rattleshirt)
Melisandre notably wears a large ruby, which she uses to do magic.
"As you will." Melisandre of Asshai took the cup from his hands and
drank long and deep. There was only half a swallow of wine remaining
when she offered it back to him. "And now you."
His hands were shaking, but he made himself be strong. A maester of
the Citadel must not be afraid. The wine was sour on his tongue. He
let the empty cup drop from his fingers to shatter on the floor. "He
does have power here, my lord," the woman said. "And fire cleanses."
At her throat, the ruby shimmered redly.
A Clash of Kings, "Prologue"
(this is Melisandre stopping herself from being poisoned)
Melisandre is probably much older than she appears:
Melisandre had practiced her art for years beyond count, and she had
paid the price. There was no one, even in her order, who had her skill
at seeing the secrets half-revealed and half-concealed within the
sacred flames.
A Dance With Dragons, Melisandre I
Melisandre is likely using a glamour on herself; we have no idea what she actually looks like.
A couple of additional notes:
Melisandre is likely not originally from Asshai but went there as an adult, and spent enough time there that she's associated with it (and purposefully promotes that image).
Yet the population of Asshai is no greater than that of a good-sized
market town. By night the streets are deserted, and only one building
in ten shows a light. Even at the height of day, there are no crowds
to be seen, no tradesmen shouting their wares in noisy markets, no
women gossiping at a well. Those who walk the streets of Asshai are
masked and veiled, and have a furtive air about them. Oft as not, they
walk alone, or ride in palanquins of ebony and iron, hidden behind
dark curtains and borne through the dark streets upon the backs of
slaves.
And there are no children in Asshai.
The World of Ice and Fire, The Bones and Beyond: Asshai-by-the-Shadow
It's therefore possible, but not confirmed, that Melisandre was indeed bought and sold in Volantis and therefore would have a tattoo. We just don't know.