Here's an idea for handling fame without adding too much in the way of rules or complications. It might suck, but here it is anyways.
How do people become famous in a medieval milieu? For the purposes of D&D and similar games, it makes sense to tie fame to deeds. Hey, if Bob jumps over a cow at the local faire, people in the village will know that Bob is famous for jumping. They'll tell others, and maybe for several villages around Bob will be known as "the jumper". So it goes with adventurers.
Since fame is tied to deeds, it also makes sense that fame is tied to XP. XP are handed out for deeds, therefore XP equals fame.
Or does it?
In our example above, everyone saw Bob jump over the cow. If Bob had done it without witnesses, and just claimed to have jumped over a cow, he might have become known as Bob the Liar rather than Bob the Jumper. So, in this system, XP only turn into fame when the deeds that generated the XP are either witnessed by the public at large, or can be proved. If you want to use this system, you'll need to put a second XP number in parentheses after the normal XP number.
You accumulate these "fame XP" by doing things in front of people, or you need to spend or display the treasure you looted, and you need to bring back trophies (at least one really good one, the gorier the better) to show that you defeated monsters or black knights or wizards. If you do these things, you count those XP towards your fame level.
Since we have a separate "fame XP", we also have a separate "fame level". For simplicity's sake, use the Fighter's XP progression in your game as the Fame XP progression. Fame levels are as follows:
The Upside of Fame
So, what do these fame levels get you?
First level fame is worth nothing.
From 2nd level onward, they enjoy the following benefits:
1) They have a percent chance of drinking for free and picking up interesting rumors in taverns
2) They have a percent chance of getting an invite to dine with notables equal to their fame level, the chance depending on the size of the settlement
3) You can employ an extra number of henchmen equal to your fame level, and their base loyalty is increased by a number of percentage points equal to your fame level
4) You can request audiences with princes, kings, emperors, high priests, etc. You have half this chance of requesting a boon in exchange for a favor, and a percent chance equal to your fame level of requesting a boon in exchange for nothing
The Downside of Fame
Fame has a downside as well. When you enter an area, your fame might proceed you. You can cut the chances of being recognized by wearing a disguise and using a different name, but lose the benefits of fame (see above) if you do so. Here's a twist - if you are moving in a group and not everyone in the group is disguised, your chances of being noticed are increased by 5% per undisguised person.
If you are recognized, one of the following happens:
Challenges: You will be challenged to a duel (magical or martial) or test of skill by other notables in the area. This will be public. Losing these challenges actually reduces your fame XP level by as much as it would have increased if you had won.
Quests: If you are neutral or lawful (good), and there's trouble afoot, you will be asked to handle it. If people have been kidnapped or there are monster's raiding the area, you are expected to solve it. If you refuse, you lose enough XP to take you down a fame level. You suffer the same consequences if you fail at the quest.
Justice: If you are chaotic (evil), you are set upon by the authorities in the area, or bounty hunters or people you wronged in the past. In other words, being famous and evil means being hunted.
For this reason, characters might discover that fame is a double-edged sword.
Nobody wants to die, but dying famous is probably better than dying unknown for an adventurer. When a character dies, the following happens:
6% chance per fame level of a folk song being composed in their honor
4% chance per fame level of a biography being written about them
2% chance per fame level of a monument being erected where they died or a civilized place nearby
For clerics, druids and paladins, there is a 1% chance of them being canonized
Now, total these honors received. This is the percent chance (thus, maximum 4%) that upon death they are received by "the gods" into their company as a quasi-deity. They can still be used as PC's, with powers deemed suitable by the DM, but only in the company of other quasi-deities or demi-deities and the like. Congratulations!