(For example if you pick a character with no driving skill and they nab a car, the character should crash a couple times and in general be unstable, but after using it for awhile and maybe killing some zombies with it he should get level 1 in automobiles. At higher levels of driving, maybe the character can get some perks when he drives, like bonus speed, maneuverability, maybe a skill he can activate.)
Same with other things, pistols, machine guns, rifles, special vehicles, melee weapons. Maybe with enough investment into melee skills you can acquire some special attacks with melee weapons.
You're having dialogue in your game? Here's an idea. There can be hermits fortified in isolated shacks across the city surviving alone. If you happen to discover them and befriend them, they can apprentice you, and give you skill boosts to whatever (depending on who they are.) Or... they could gift you with special items after gaining a certain amount of levels. (I.e. silenced shotgun after being under them for 10 levels.) Of course a lot of these "masters" should be in populated areas. It could be a character integral to the main quest, and when you do all the dialogue related to the quest, you can come back he will teach you his perks.