Updated 9-14-14
This will be edited as I fill the list. Some of these have conflicting sources on how much they are raised, I will try to confirm what I can.
Updated Dragon's Training, a total of 104% can only be obtained by having your final training at 99%.
Arroyo
Cameron - Raises Unarmed and Melee by 10% Only with an Agility of 6 or less, and none of the 6 combat skills can be tagged.
Lucas - Raises Unarmed to 55% Only 40% if below 40%
Jordan - Raises Melee by 10% Must have at least 35%
Klamath
Slim Picket (Trapper Town) - Raises Outdoorsman by 16% for $100. If you don't get the option when asking about geckos, just keep trying and eventually he will offer. With a high enough speech check, he will sometimes offer for $50 or ask for sex from a female player.
John L Sullivan (Golden Gecko Bar) - Raises Unarmed and Melee by 10%
Smiley - After saving him from the Toxic Caves and gaining Gecko Skinning, speak to him about Gecko Lore to raise Outdoorsman by 1-6% From the multiple tests, it appears to give you a higher percentage if you actually sound interested in what Smiley has to talk about. "Gecko Milk? I thought geckos were reptiles." and "Teach me, oh great trapper." seems to reward 5%, the latter options where you say something along the lines of "Oh, yeah? Keep talking." gives only 1%.
Vault City
Dr. Tory (Vault) Speak with to receive Vault City Training perk, raises First Aid and Doctor by 5% A Doctor skill check of 75% is required.
New Reno
Renesco (Renesco's Pharmacy) - Take the spectacles which can be stolen from the Professor's Radscorpion in Broken Hills, then give them to Renesco for free (not taking a discount or reward). You then must ask him 20 times, "How are the glasses working?" before he will become annoyed with you and throw the Pip-Boy medical enhancer at you. Use it to raise Doctor by 10%.
Miss Kitty (Cat's Paw) - Choose "Just Talking" option to raise Speech by 3% Only 2% if tagged.
Miss Kitty (Quest) - Delivering 10 copies of the Cat's Paw magazine will reward you with Cat's Paw No.5, using this will add 10% to Energy Weapons
Lil' Jesus Mordino (Desperado) - Raises Melee 5% if approached with a knife in the active weapon slot and then paid. If you are a female with Cha 6+, you can sleep with him and earn a bonus 5% if you 'perform' well.
Mason (Salvatore's Bar) - Raises Energy Weapons by 5% Louis Salvatore must agree to give you a Laser Pistol, Mason will then offer to train you.
Punching Bag (Shark Club Basement) - Use to Raise Unarmed by 5%
Leslie Anne Bishops (Shark Club) - Once you sleep with Mrs. Bishops, you must follow the dialog branch when Vault City is mentioned to obtain the Pip-boy lingual enhancer, this will raise Speech by 10%. An Int of 9 is required to open the dialog option.
Stuart Little (Jungle Gym) - Becoming a Prizefighter will raise Unarmed by 5%
Broken Hills
Bill (Downtown) - Picking up Brahmin dung 5 times in a row gives you the Expert Excrement Expeditor perk, raises Speech by 5%. Must have an Int of 4 or less to get this option.
Sierra Army Depot
Punching Bag (Level 1) - Use to Raise Unarmed by 5% Only 4% if tagged
San Francisco
Dragon/Lo Pan (Chinatown) - You can train with Dragon (Karma 250 or more) or Lo Pan (Karma -250 or less) to raise Unarmed by 5%, can be repeated every 22 in game hours to a max of 104% (Last trained at 99%) but only a total of 20% gained. It is possible to learn from both Dragon and Lo Pan, if you can do enough to change your karma. Doing this can net you 40% total.
EPA
Kitsune (Blue Level) - Once Recruited, you can speak to her about personal story to raise Lockpick, Steal, and Sneak by 10%
Dex (Blue Level) - Once Recruited, you can ask him for tips to raise Speech and Barter by 15%
Cat Jules (Blue Level) - Once Recruited, you can ask him for training to raise Small Guns, Big Guns, and Energy Weapons by 10%
