It seems to me that the visible/hidden trait idea could work quite well, if the price and upkeep was reflective of the visible traits — Early on, you may have to settle for a short knave or peg-legged deserter due to lack of money, and once you had developed his abilities, you may not want to replace him with someone else. This would be especially so if mercenaries could gain good traits from battle. For example, many repeated battles with no losses could result in a trait that gives “confident” morale level at the beginning of every battle.
If the player becomes attached enough to their initial band of misfits, they will not feel so inclined to replace them with more traditional “cookie-cutter” soldiers. I believe this is the intended effect and would lead to both great story-telling, but also meaningful decision-making: Early game, the player would have to choose between a large number of practically incapable men, or a smaller number of slightly incapable men; Mid/late game, the player would have to decide whether to replace his battle-hardened misfits with unfamiliar professionals, maybe even for a morale penalty with the other men!
Additionally, the hidden traits (dastard and gluttonous are good examples) would be present in all varieties of men, leaving the aspect of risk/gambling somewhat untouched — this may be yet another incentive to stick with your misfits: Who can tell if that 5000 gold, tall, strong soldier is also a craven pig?