I love the concept of stamina, but just to shut up all the "We hate stamina!" people out there, implement a "minimum" stamina, where your troops will still be able to fight (though have to rest to regain it), but at only 60% effectiveness or something.
I think that the only way of recharging stamina (without magic, items etc) should be to not do anything. Walking/marching should freeze stamina regeneration, fighting should drain it, and sprinting/charging etc should drain it fast. Having a hero to lead the charge could maybe affect this?