If he's Half-orc, Bloodfury Savage lets you reroll Intimidate.
Traveler's Harlequin allows multiple multi-class feats for more skill training.
Glorious Myrmidon (Fighter) gives +1 speed, +2 Acrobatics, Athletics and Endurance.
Darksun has a lot of nice options for double rolling skill checks, assuming you allow themes (or are willing to forgo that requirement).
Unwelcome Guest (Athasian Minstrel) lets you roll twice for Bluff, Stealth, and Thievery checks.
Arms-Troubador (Athasian Minstrel) lets you roll twice for Acrobatics, Athletics and Stealth. And if you fail by 5 or less, doesn't count as failure in skill challenges.
Rainbringer (Elemental Priest) can roll twice for Endurance, Heal, and Nature.
Freedom Fighter (Escaped Slave theme, or Warlord) gains and grants (to allies within 3), +2 bonus to Initiative, Perception, and Insight.
Caravan Master (Dune Trader) rolls twice for Insight and Perception.
Shady Dealer (Dune Trader) lets you roll twice for Bluff, Diplomacy and Streetwise. And if you fail by 5 or less, doesn't count as failure in skill challenges.
I might be missing some. You could also look at some skill powers like Secrets of the City, Arcane Mutterings, Legend Lore, Damning Secret, Try the Stick, etc.