Then I forgot about it.
Then I remembered! So, here's a process for generating characters, backgrounds, and setting:
1. What part of the campaign setting is your character from? Civilization, Wilderness, Sea, Underworld, Other?
2. Roll 2d4, in order, for each attribute.
This is you as a child. What sort of a child are you? What trade were you raised with?
(You can google up a list of Medieval occupations for inspiration.)
3. Make up a location and an NPC for the campaign setting.
4. Roll 1d4, in order, to add to each attribute.
This is you as an adolescent. How have you changed since childhood?
5. Pick a class. Who trained you?
6. Make up another location and NPC for the campaign setting.
7. Roll 1d4 for each attribute and assign as desired.
This is you, as of a few months ago. What are you doing with your training? Describe a meaningful memento in your possession.
8. Make up another location and NPC for the campaign setting.
9. Determine one attribute randomly (1d6). You get a +2 bonus to this attribute and the player to your left get a +1 bonus. Make up a two-sentence adventure where the use of this attribute saved you and your friend.
(You can use an adventure plot generator, such as the one in the D30 Sandbox Companion or google something up.)
If your game uses skills, then Where Your Character Is From counts as a broad indicator of competence, and the Trade They Were Raised With is a specific skill set. Otherwise, it's just more lovely fluff.
I think the numbers work out better using 4d4 +3 bonus points, but there is a strong impulse to stick with the iconic 3d6. In which case, just roll 1d6 at each stage, and don't award points bonuses for the Adventure With A Friend. Or maybe just a +1 bonus to the character being generated.