(I'm not feeling well today so this may be a bit disjointed.)
I was thinking that perhaps some of the scenarios could be used as a basis for quests that would enable heroes. Maybe instead of just being building heroes, one would have to do something to actually get them. Either that or have new semi-civ specific heroes on top of what we have now.
I know I'm not articulating this well but I'm thinking of Decius. If he isn't in the game as a leader, the Bannor, Malakim or Calabim could get a quest involving him. For the Bannor, you'd have to send him on a trial to prove his innocence. For the Malakim, it might be to prove he's not some sort of wolf in Hero's clothes. For the Calabim,
http://forums.civfanatics.com/showthread.php?t=322196 shows that perhaps he'd have to go defeat some hill giants.
Perhaps it could be something less move a unit around but do something to unlock him. For the Calabim, they'd have to accomplish a hard espionage mission to 'corrupt' him. For the Bannor maybe you would have a "Decius" unit and you'd have to get him to the Pool of Tears to purify him and have a certain amount of time to do it otherwise he'd leave.
Anyway, I was just thinking a some of the minor leaders or great generals (I'm thinking of Rhyianna the Witch-lord) would be cool as a sort of separate hero like Korianna instead of just being great generals.
Another idea is (broken record time again) if a commander system (either FF or my favorite, the HoTK system) is put in perhaps a Civ still gets great generals like normal (which could be used as they are now) but to get a great commander (which can build armies) you need to complete a quest to get that hero.
Now since the AI is ********, perhaps if a AI Civ gets a quests, they'd have a flat % chance to complete it so they'd have access to them as well.