Some players (Satine, I'm looking at you) do like to mechanically customize their characters.
Some other players (and most DMs) do not like to keep track of all the fiddly bits that begin to accrete around a PC when s/he begins to mechanically customize his/her character. Plus it can make the game more about hunting around products looking for customization options than hunting around dungeons looking for adventure.
So, what about this: Different places in the campaign world have different levelling-up options.
That is, different cities, dungeons, lonely mountain-top-temples, etc. have specific people there able to teach certain skills rather than whatever the standard levelling-up scheme is in whatever system you're using.
i.e. level up to 3rd level as a barbarian in Gormatia and you'll be able to ride a lion as a steed, level up to 3rd level in Sundervist and you'll get 2-weapon fighting, level up in Gon-Jiin and you'd get an extra kung-fu number, do it in Nornrik and you get the ability to freeze the blood of 0-level characters with but a baleful glance. etc.
The PCs have to know this in advance in order for it to work--i.e. the DM has to let everybody know what fiddly bits are likely to be learnable in which part of the world and there have to be enough different options that it's genuinely a choice rather than merely a bunch of obstacles in front of the PC before s/he can get her new chunk of badassness.
(You could do this as "learn a specific skill" or "learn the whole package for that level" depending on your system.)
This kind of thing is informally present in lots of games and in many parts of D&D (finding spells is an obvious example). AD&D is notorious for having levelling-up requirements involving finding certain people (that everybody ignored) like how druids have to find and kick the ass of some specific other druid in order to level up at all--I would avoid that. The idea isn't that you can't level up unless you go someplace or do something, merely that if you want a variant option then you'd have to visit some new and different land and have an adventure to get there.
The idea here would be to formalize and standardize it enough that it was a basic feature of every place in the campaign world. Each place would have some special talent attached to it and whatever kind of skills were available there would say something about the kind of place it was and provide adventure hooks. Why is it that only the mages of Arglobgoon know how to teach 5th-level biomagic? Why is it that only the monks of Orgorf know the art of the Four-Finger-Demon-Dispatch?
It also lets the DM slowly slip in customization options to a relatively simple system slowly over time--as the world gets explored and as s/he figures out how the new fiddly bit works--rather than having to make decisions early on about what's in and what's out and then risk being unfair by moving the goal posts later.
This makes it so that rather than having a pre-requisite number of levels or ability scores in order to get a fancy class (a la traditional prestige classes), you have to have some sort of pre-requisite adventures.
Or: it makes the later-level character-build options work more like magic items. Which is pretty much what they are anyway.