I think I'll go the battle cleric route. Here's the background:
Rowena was born the only daughter of The Lord Mayor of Elredd, on the wild coast, in CY 570. Her three older brothers each was destined for a post in the government, but Rowena’s best hope was being assigned a husband who wouldn’t beat her. Her eldest brother, Sigmund, was a redoubtable warrior, 10 years her senior. Her second and third brothers, Karl and Dane turned out to be more of playboys. When the wild coast was attacked by the forces of the Pomarj, she didn’t recognize the danger, and didn’t flee in time. The Elredd militia was no match for the orcs hoards, and Rowena was captured. She endured a brutal, harrowing week in captivity. Then one night, she was shaken awake. It was no brutal orc shake, but the gentle touch of love. Looking up, there was her eldest brother Sigmund. He had escaped the battle, hidden in the Suss forest, and now returned to rescue her. After a week of hunger and fear, slipping through orc patrols, they escaped to Verbobonc, where her brother Karl and others of the court had fled. Her parents and Dane had been killed in the battle and subsequent slaughter.
Having escaped, she realized the worst of it. She was pregnant. Young, foolish, and full of shame, she concealed her condition as long as possible. Finally, she knew the baby would come soon. Unable to face her family, she took a horse and fled the city. She tried to escape into the hills and woods to labor, and perhaps die alone. But it was not to be. Seeking a quite grove, she stumbled upon a group of Hextorites, who had fled Fax, when the city, and their temple had been overrun by humanoids. Seeing the young woman come in, obviously about to give birth, the leading cleric took charge. As she lay and labored, he extorted her to embrace the pain. “What does not kill you makes you stronger!” he insisted. In the haze of her embarrassment, her fear, her loneliness, she found strength in this stranger and his harsh philosophy. Only through strength and ruthlessness could she strike back as those who made her suffer. Her screams of pain resembling shouts of triumph, she pushed out her child, a healthy half-orc boy. She named him Vengeance. The boy was welcomed by the cleric, who foresaw a brutal future in this child, so oddly placed in his hands.
Rowena felt unable to return to her people. Instead she stayed with the Hextorites. Their ways were harsh, but seemed appropriate to her experiences. Their leader, Garth Spiker, took Rowena under his wing. He had been impressed by her attitude in her hours of trial, and expected great things of her. He promised her the power of Hextor could be hers, for use in her vengeance. Pain, hatred, vengeance. These were things Rowena now embraced.
As to how she comes to encounter the party, I don't know, so I'll leave the last of the story for later. She would be a human cleric of Hextor, with War and Destruction as her domains. She's LN, not evil. She hates the humanoids, Iuz, and the scarlet brother hood for starting the wars. She has no interest in the slaugther and torture that so many Hextorites enjoy. But she does embrace his harsh, survival of the fittest, aspect, and sees her life as an intrument of destruction.
I've started stating her out, but I thought I'd see if she'd fit first. The Paladin will put up with her, hopefully, as she's not evil, and he doesn't worship Heironeous. If it looks like she won't fit, though, no problem. I could retool her fairly easily to be a cleric of Trithereon, say.