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.