Or one could with the Military Academy recruit(or it acts like a trigger for random gains) these kind of leaders. And maybe get to name them ?
Military Academy could be new building in town but it is not necessary (look below):
These leaders are normal army but can gain experience and they are more expensive.
2nd way is make all leaders in game to gain experience and do not create leaders like above.
3rd way is make army exp too