Thank you for all of the help and thoughts. I think I will end up going with a 'regenerating while you walk' design in this case.

If anyone wants to check out the game so far, head over to www.necromancergame.com
There's a blog, some early art, the script for the intro chapter and more.

Hmm... the goal is to collect undead minions and the like, right? What if you have it so that your minions heal up depending on how many "leftovers" remain from the enemies you fought? Like, if you destroy an enemy skeleton in 1 hit then (theoretically) more of the bones would be intact than if it took you a bunch of hits. The more "intact bones" remain after a battle, the faster your own minions can heal up after each battle (by basically cannibalizing the parts of your enemy).

Of course, it might be best to abstract it, maybe through a score system. You get "necromancer points" for defeating your enemies quickly and without damaging them too much. So having skeleton warriors quickly stab your enemies leaves intact corpses and thus wins more points, as opposed to something like blowing them up, setting them on fire, or using special "holy" magic or whatever.

So, in addition to getting experience for defeating your enemy, you also gain necromancer points for defeating them in a certain manner. If you play smart and win alot of necro points, then at the end of combat your minions automatically heal a large amount of points.

Some players might fight using lots of explosions, fire, or smashing attacks that defeats their enemies quickly but destroys their remains. Others use "safer" methods that might be harder but leave more bones behind and as a result they let their minions heal up more after each fight. In addition, recruiting enemy units to your side obviously doesn't leave any remains behind (since they aren't destroyed) so there could be some strategy involved with recruiting monsters. Do you recruit lots of enemy undead you find, or destroy them to repair your undead army? Actually, there could be a mechanic for sacrificing some minions to get more "bones" to repair your other minions... perhaps there are some monsters who are uninspiring in combat but have the notable feature of leaving behind lots of bones when sacrificed? Keep a few of them on your side mostly to store bones and then sacrifice them in or out of combat for a quick way to heal up your more important monsters.