goblinoidgames.com

Two ideas:

Tie skills directly to stats and make them the skill checks. So, for instance, a "how to use skill" might be an INT check with bonuses, or a repair skill based on DEX, or a negotiate skill based on CHA, or even a SERE skill based on CON. Races, levels, and mutations might influence skills as well.

Secondly, give XP for all encounters. Fleeing an overpowering foe, figuring out how to use an old gizmo, negotiating a peace agreement, or saving a family from a flash flood could all give experience points. The GM has a range (like Malcadon suggested) and points are awarded as usual, just not only after combat. This would change the game from combat/treasure-based to exploration/interaction based, so it might not be the best idea.

White Wolf's Exalted has 25 skills, or as they call them abilities. Theses abilities are Archery, Athletics, Awareness, Brawl, Bureaucracy, Craft, Dodge, Integrity, Investigation, Larceny, Linguistics, Lore, Medicine, Melee, Occult, Performance, Presence, Resistance, Ride, Sail, Socialize, Stealth, Survival, Thrown and War. In a d20 or retro clonesque system you can easily Archery, Brawl, Melee and Thrown, regular combat rules plus feats and or weapon mastery/class features cover those. In pre-d20 Awareness, Larceny and Stealth can also be folded into thief skills with a total of 18 skills left, with Athletics giving a boost to climb sheer surfaces. Now divide them into four categories and this is what you get.

Physical - Athletics, Dodge, Resistance, Ride, Sail and Survival
Social - Bureaucracy, Integrity, Performance, Presence and Socialize
Academic - Linguistics, Lore, Occult and War
Technical - Craft, Investigation and Medicine

Maybe Dodge would be best reflected by incremental AC as a class feature. That still leaves 17 skills left.