RyaReisender: Final Fantasy 2
SaGa (Final Fantasy Legend) 1+2
Romancing SaGa 1-3
SaGaFrontier 1+2
Unlimited Saga
Romancing SaGa Minstel Song
The Last Remnant
The Legend of Legacy
Emperors SaGa
Imperial SaGa
Wizardry 8
King's Field IV
...are the ones I remember.
Sarisio: Problem with Saga, Last Remnant and Wizardry 8 is level scaling. Wizardty 8 doesn't fit your description as it is better to do level suppression and do other counter-intuitive things. FF 2 comes close to solid system though. Legend of Legacy is yet to be localized. King's Field looks more like Action game with RPG flavor.
I thought about something akin more to EverQuest 1 or even Ultima Online systems. Level scaling simply ruins all and any system of character progression.
There are also Wizardry VI, VII which had skill system and no level scaling, but biggest chunk of characters' power was from level (->HP, stats, spells, etc.), not skills.
So it leaves us only with FF 2 as a game with somewhat solid skill-based character progress system.
I mentioned the SaGa 3 DS remake. SaGa 2 does this (for humans and Espers (mutants)), but the growth is too slow for my taste. (My fastest playthrough of the SaGa 2 remake was with 2 robots and 2 monsters.)
SaGa 1 does not do this. Humans gain stats solely by using buyable consumable items, and monsters transform with meat. Espers gain stats and skills after battle, but it is determined solely by the game's RNG rather than by your actions. (The RNG in this game is so appallingly bad (to the point of making casual play less fun) that I hesitate to call it "random"; in fact, when soloing SaGa 1, I have actually used luck manipulation to get past Ashura.)
Edit: Some other games I thought of:
Hybrid Heaven (Nintendo 64) does this: Use a specific body part a lot and it gets stronger. I believe there are even visual changes. (My favorite attack in that game is the head butt attack.)
The Quest for Glory series also does this. This case is interesting because there are a lot of non-combat skills such as climbing.