If you like the Underdog normals, you should know that my current character is a former 0-level henchman and the most veteran character in the group (I borrowed someone’s henchman a couple times when my normal group couldn’t meet, when that group disbanded, I was granted the character permanently). John, son of a fisherman, the henchman who lived, now is one of 2 3rd level party members in a group of mostly 1st level PCs and has the groups most powerful divine and arcane casters as henchmen. He has 24 hp in a group where 7hp is the 2nd highest (except for my caster henchmen who have 10 and 11 hp). He wields a magical sword and has fallen only once in battle. There are jokes that the campaign will turn out to be the Hero’s Journey of John.
As for class-leveling, I don’t think any normal man should get something like casting just out of the blue, regardless of intelligence. Normally it takes months of study with a 9th level mage to have a chance to become an arcanist, a week adventuring with a 1st level mage or two shouldn’t really cut it. Clerics should require similar devotion. Scoundrel types can be obtained through the carousing hijink, but similar jobs might get you there. Still, there should be some limitations on advancement, this isn’t 3.x D&D, this is a semi-realistic system.