Non-Linear Phenogram of Battle Initiation

[MechanicalPen]

Have you considered not having levels at all? It sounds crazy, yes but the whole point of levels is to give a sense of progression and to wall off content (or to let the player grind to compensate for their lack of skill). Since you are already giving the player a sense of progression through recruiting, levels may not be necessary.

It sounds like monster scaling is your best bet if you do not want to get rid of leveling.