Imagine a player wanting a training in leadership by some charismatic nobleman. I am the GM and I agree with that, but I have no idea as to the time spent and the monetary compensation it would take. Is there any information regarding this, or any rules of thumb ?
As a general rule of thumb, about 3,000-10,000 gp.
There are a few things that grant feats for money, and exactly how much it costs is going to depend on how powerful and useful the feat is. A good starting point would be the Legendary Sites starting on page 142 of the Complete Scoundrel. They all gives permanent or long-duration buffs that have an "ability value" that is roughly how much WBL finding that location is worth.
As an example, visiting the Court of Thieves location is worth 6,000 gp, and gives you a luck feat of your choice.
If what you're trying to do is give your player the Leadership feat in exchange for money, then you probably want to charge somewhere in the 5,000 - 10,000 gp range. Leadership is pretty powerful under the right circumstances, so it probably should be in the higher end of the 3k-10k range.
You could also use the Retraining rules on p. 192 of the PHB 2, and have the player lose a feat in exchange for Leadership. Retraining a feat can be done without cost, but if you want to charge for it, it takes 2 weeks, and costs 50 gold.
To answer literally the question asked: Arms & Equipment Guide suggests that feats should cost between 3,000 gp and 15,000 gp. This handbook lists most (all?) published options, for comparison. Leadership isn’t on there, but it may be useful.
To answer the more general question of “what to do” in this situation: the game assumes that PCs are, during downtime, studying, practicing, or training (and taking care of equipment and cooking meals and so on for any other necessary activities that you may not explicitly devote “screen time” to). They can do this on their own or with a hired trainer, but they’re doing it. That’s why they get better. Leveling up represents that “eureka!” moment where it all comes together for them, and they can use these new or improved skills. In this case, the training with the nobleman explains where the Leadership feat came from, rather than it just suddenly appearing on a character sheet.
So what the game itself suggests for this kind of situation is for the player to just take it as a feat at the next opportunity.
Realistically, of course, that might be three levels away, which is a very long time. So don’t think necessarily that it’s “wrong” to allow trading gold for feats in limited ways. For that, see the first section.
For the case of Leadership in particular, however, I’m going to suggest that the feat should be, well, priceless. And that includes the price of “1 feat.” The Leadership feat can be extremely powerful, and gives the player a lot of “ownership” and “rights to” an NPC. This is problematic because a cohort can effectively double one’s actions, allow cheaper equipment through crafting without any loss of personal prowess, and so on.
As such, in many games I play in, and all games I DM, Leadership is banned. If a player wishes to have a sidekick, they can find a suitable NPC, and roleplay the relationship with that NPC, convincing them to join the party (or explicitly be assistant to the PC), negotiating loot shares, and so on.
Because the player didn’t spend a feat (or gold) on it, this NPC is much freer to be independent, including leaving if the player is unreasonable. And it also means that they are limited to NPCs you make available to them, rather being able to basically order whatever they want as Leadership suggests. If they really have something specific in mind, they could put up posters, host auditions, or attempt Gather Information, but it’s all very much part of the game itself, not just taking a feat.
So I suggest that you simply make this, effectively, a side-quest.