Well, hrm. I think I'll try and help out here a bit. Given the limited number of starter classes, there should be a diverse hierarchy of classes to acquire.
Since you start off with Knight, Warrior, and Mage, these three classes must have the most basic skills. No fancy fire explosion skills or disembowelments just yet. xD It would be better to upgrade heroes, instead of unlocking them, because you retain the effort spent on the original hero. Yet there is value in retaining the skills of old classes for certain tasks, so there's that to think about.
In terms of upgrading, though, I think a system like the one in FF:Advance might just work, but I'll hybridize it and create two possible options. Here are the details(If I remember them properly xD):
So say I start out as a Knight. I get my skills, level up in battles, and get points, and eventually get a Mission Scroll. Each scroll presents a different scenario, so let's say this scenario involves protecting a pilgrimage to a shrine. Upon completion of this scenario, the Holy Order blesses the knight with heavenly knowledge, giving powers to banish evil, etc, etc, I becomes a Paladin.
As a Paladin, I can retain the skills of the knight, but also gain a set of three new skills, which follow my theme. And so I can fight on, get a Mission Scroll, and advance to a final class (or however many you wish) in this way. I would say 5-6 skills should be the maximum, so there will be choices to be made as for what skills to keep. This is one path of upgrading/unlocking. (Vertical: 1-->2-->3)
The other path is far more complex, however, and represents mixing between classes to create entirely new classes.
So I'm a knight, again, and I go through all the hubbub to find a Mission Scroll. Let's say I have the pilgrimage mission again, but instead of proceeding to the next level of my class and becoming a Paladin, I choose to class tech horizontally back into a Mage. In doing so, I can retain one skill from my past class. Then more fighting, points, etc, and so my Mage gets a Mission Scroll. For the sake of ease, we'll say it's the Pilgrimage mission again.
Now here's the complexity. The game acknowledges the mage's past career as a knight for upgrades, so new paths and new characters may open up. As for which paths open up depend not only on the types of characters played, but their specific order. In this particular instance, the Mage could have become a Battle Priest, but if we switch the order, then the Knight could instead turn into a Paladin or something else, depending on the mission.
This is the other way of upgrading. (Horizontal: X-->Y-->XY)
That's just a brainstorm I did, but I hope it's clear enough. ._.