If you ask me, the real issue here seems to not be the rate of which skills are learned, but the fact that someone can become a legendary warrior through training alone.
Perhaps the solution would be to limit the effectiveness of training - maybe the skill boost while only training could be reduced by your own personal skill level - and maybe boosted by the other person's skill level, but I personally believe that should apply to any combat situation.
This would probably end up looking something like this:
Say you'd normally earn 20 EXP for hitting somebody. Now let's say you're hitting a skill level 20 combatant. For sake of ease, we'll say this just increases the EXP gain to 40. Now let's say you're skill level 5, which would be, if I recall, effectively untrained. This could mean your EXP gain is unreduced. Now let's say you spar with this fellow again later, at skill level 8 (3 into being trained... I think that's the adjectiveless level, but I could be wrong). That would reduce you by 3*3=9 EXP, so you'd gain 31 a hit (for training with someone who's awesome, of course.) Eventually, you reach skill level 12, and the reduction becomes 49 - you no longer will gain EXP from sparring with this fellow. But you still would if you ever had to fight him for real, of course.
Let's rewind a bit. You're level 8 again - the reduction is 9 points. You spar someone of equal skill, so you'd normally gain 28 EXP. But you only gain 19 EXP, because you're only sparring.
Of course, those numbers have no actual bearing on how the system will end up - they're just me trying to give my idea some meaningless figures.
The real idea behind it is that lower skilled combatants would spar to gain EXP, while higher skilled combatants would gain no or very little EXP from it. (maybe there'd be a minimum or a chance at a minimum of 1 EXP gain per hit or something) So, why would the higher skilled combatants spar? To train the lower skilled combatants. Presumably, some soldiers (particularly veterans) would gain some amount of enjoyment from sparring. Plus, if there's ever a skill decay system put into place or something, sparring could easily be used to thwart that off.
It'd also, you know, reduce the amount of legendaries created from just sparring. You'd have to put your life on the line to gain legendary status, now. Kind of like adventure mode. Maybe there should be a "Subdue only" option for military squads, too, that way they can spend hours and hours on end wrestling and trying to knock zombies out, buahaha.