I`m not sure that would work. Many players like to try different things, but if they get restricted about using all units in game that could be problem in trying other army builds (expl : you want to go dragon army and use units to achieve that, and when you get dragons more than half game is gone, and if you want to try some other unit lineup there is no more enemy units for you to achieve conditions for it, as i said when you start game in KB enemy are all already positioned, and no more spawning).
As for medal advancement, i thought better solution : to make more diversity in medals, since in AP/CW of 10 medal only 2 are different between hero classes. When you get some medal it unlocks 2 other, and after you lvlup 1 of them other is locked, but you get 2 new medals (like branching skill tree, when you get medal lvlup be sure what you want before choosing which direction to go). And same would be great for skills, more class specific skills. Now we have 30 skills, and only 2 class specific, not much diference between heroes

Csimby had nice idea to get skills to 4-5 lvl, same as medals got those lvls, but i thought to get warrior 5 lvl skills in might tree, paladin 5th lvl in mind, and mage 5th lvl skills in magic tree. This would give us more class oriented play.
And last, rewards from quests to be choice : some item or runes or bonus exp. I love this game, it`s great in possibility for playstyle, but everything is predetermined on starting new game (all enemy/units/items/rewards . . . is known from start, and with savegame scanner you see is it worthwhile to play or not. no need to even get out from first location, if you dont like that savegame file, just restart and scan next to see will you play).