Cults. Evil societies. People living in the wilderness. Hell, Forgotten Realms has a whole area that has a lot of Elf or Orc versions of Tieflings, because demons in the area overtook a castle and the surrounding countryside and had specific breeding programs.
More reasonably, I'd say the Warlock or something appropriate. "My dad made a pact with a demon and it infused his body with the demon's powers. And that power carried over in his bloodline to me."
As for "bringing baby Neeshka to the towne faire", how about "exercising the Disguise skill'? Or even more likely, the Tiefling's fiendish appearance doesn't surface until it hits puberty.
The creator of Eberron suggested some Setting-specific origins for Tieflings; they're not from breeding with Fiends, but from births that occur when a plane is lined up with the stars and the Plane itself is touching the immediate area. And the tief's personality corresponds with the Plane that they are tied to - a Tief born when the Plane of Fire is in line with the site of his birth is passionate, chaotic and often fire obsessed. Tieflings could also come from births that occur in proximity to sites over-rich with dark magic (the Underdark, Mournland, etc).
I mean really, if you're going to go that far, how could Half-orcs be allowed to survive, since they're always the product of rape? Or wizards, because we're operating on an uneducated, pre-industrial society? If anything, necromancers would be mobbed on sight.