I had my players make use of the "7 Sentence NPC" to create a basic concept. Those that were really interested wrote a complex background and gave me possible hooks for future campaign tie-ins. Those that just wanted to play around still had a good framework for a character, but wouldn't find as many hooks for their character's development.

My world was still flexible enough that I could incorporate a number of disparate origins into a single setting: a goliath tribal country to the north, roving bands of catfolk and saurian shifters in the mid-country, and a warforged glamored to look like a grey elf (with a memory problem). Two of them are seeking revenge (murdered mentor, murdered spouse and kidnapped child, and though they don't know it yet, it's against the big bad of the campaign.

However, I'd second and third eepop's advice about making sure they have a reason to fight together, not just fight. My players were "the only ones around who were capable enough to deal with the threat", but that was a weak step early on in the campaign.