Start with a quickly fading really messed up dream and then only keep the story. As time goes along, pitch only the characters and settings to others and watch as they come up with stories. Take pieces, both the good and the bad, and make them excellent. Character development comes naturally. Have some characters that doubt each other? Have some characters witness deaths? Have characters trip over that sealed evil in a can? Of course they're going to get messed up. Possibly it comes from the fact that I treat stories I hear as real.
When I make open-ended game, they are not open-ended. They be very not open ended because story not very open ended. Story has begin and end. In between not matter, like babies who are dead in ground for many year in Siberia. So, I make begin and end very good. Good like the Vodka. In between focus on game. Story, not so much.
Kidding. The middle is good too. For a game, though, stories must be spotty. If the player has no control, where the heck is the game? If there's no control, aren't you better off making a web comic? In my current game, I didn't get a plot down until too long ago, but it constantly changes as the engine improves. For example, instead of a single evil in a can, now it's like a soda of evil that was shaken up over the course of a few thousand years. The new weapons change the amount of soldiers chasing you down, the dialogue between characters, the reason for not being able to get off an island when the can of evil pops open. The changing of the source of the ruins to a more recent civilization changes the area, the platforms, the secret weapons, the giant clock, and the technology in the ruins. All of this is the middle. None of it is set in stone.
Now since the player doesn't know this world at all, and is going to be discovering it as they go, why would their character know anything about it to start? No, this is not the amnesia thing again. The character comes from another realm.
And, for this project at least, that's another reason why I don't have to set it in stone, as the same exact thing is happening here. From a USA just out of the Civil War, a world with elves ironically without magic, the character I've got is suddenly thrown into a Steampunk style post-apocalypse Old West through the world with a lot of magic, guns, fusion engines, a few shapeshifter beasts that are faster than shadow, and a five person ensemble? Fuck no, not setting any of that shit in stone. Play it by ear. I'll piece together a rough story months before work starts, but if it's not about the player, if it's not working out with the engine, or if it's not fun, I'm not afraid to nerf a storyline that I just spent a couple months setting up. The end, that may be set in stone, but even then, an ending like that no longer seems as shiny.
Half Life 2 anybody? How about even Duke Nukem Forever's storyline over the years? More than several storylines on both of those, very much destroyed completely many times.
---
Oh yeah, but practicing daydreaming helps insanely. That, and I really like ad-lib-ing stuff.