Do they? Can't say about R'hllor, but I haven't seen any proof that the "Old Gods" would demand human sacrifice. Seems like a big misinterpretation like the whole Old Gods deal altogether, because they aren't actually gods.
Yes, it becomes evident in ADWD that the First Men made blood sacrifice to the heart trees, gods or not.
“Then a long cruel winter fell,” said Ser Bartimus. “The White Knife froze hard, and even the firth was icing up. The winds came howling from the north and drove them slavers inside to huddle round their fires, and whilst they warmed themselves the new king come down on them. Brandon Stark this was, Edrick Snowbeard’s great-grandson, him that men called Ice Eyes. He took the Wolf’s Den back, stripped the slavers naked, and gave them to the slaves he’d found chained up in the dungeons. It’s said they hung their entrails in the branches of the heart tree, as an offering to the gods. The old gods, not these new ones from the south. Your Seven don’t know winter, and winter don’t know them.”
Davos could not argue with the truth of that. From what he had seen at Eastwatch-by-the-Sea, he did not care to know winter either. “What gods do you keep?” he asked the one-legged knight.
“The old ones.” When Ser Bartimus grinned, he looked just like a skull. “Me and mine were here before the Manderlys. Like as not, my own forebears strung those entrails through the tree.”
“I never knew that northmen made blood sacrifice to their heart trees.”
“There’s much and more you southrons do not know about the north,” Ser Bartimus replied.
And there is Bran's vision:
a bearded man forced a captive down onto his knees before the heart tree. A white - haired woman stepped toward them through a drift of dark red leaves, a bronze sickel in her hand.
"No", said Bran, "no, don`t", but they could not hear him, no more than his father had. The woman grabbed the captive by the hair, hooked the sickle round his throat, and slashed. And through the mist of centuries the broken boy could only watch as the man`s feet drummed against the earth... but as his life flowed out of him in a red tide, Brandon Stark could taste the blood.