One idea that strikes me is that, at the beginning of the game you might be given a list of (probably-or potentially-atleast somewhat randomized) "quests" for your character to go on.
Pick one, and from the start of the quest, you'd be given choices and put into situations (that would themselves generate choices) that would define your character more and more, until at the end of the quest (whatever it may be/result in), you'd be fully integrated.
If you didn't like those particular quest options, you could always restart the game.
The quests you'd be presented with might use/be based on, your character's selected skills, species, age, whatever, as "seeds", and then different locations, organizations, important/historical figures, whatever, could be mad-libbed in, possibly from a list of semi-defined semi-generica.
Once you'd selected your quest, the world could generate itself around the quest selected, and around your character (either generating, or possibly allowing the player to make choices about, your character's life before that quest, and personal history), in such a way that your character would have a place in the world, and-in atleast a very tangental sense-be the most important person there.
The results of the quest-once decided by your character's actions and successes/failures-would provide an immediate "stepping stone" out into the greater world.