Hey there,
When you say hirelings, do you mean regular everyday people who the PC can literally hire to do jobs for him? If that's the case, there are a few places to look:
Page 105 of the DMG (3.5) gives some rules on hiring people for tasks and includes a table of daily wages for some basic hirelings. If your looking to have this hireling make actual skill checks to determine how well they do their job, p. 154-155 of the DMG II goes into detail about "better than average" hirelings and provides a table that breaks down a hirelings skill modifier per level and includes the wages for such hirelings as well.
This way, your PC doesn't have to train them since trained individuals are already available (assuming, as the DM, you say they are).
If they aren't hirelings, but instead are followers (as in, from the Leadership feat), you could simply work with the player to determine what kind of followers he wants and then designate them as such - using the NPC classes and then determine their main skills on the principal that the character spent some of his downtime training his followers and it's represented by their ranks in that skill.
Hope that helps,
J from Three Haligonians