Fate Core, and other Fate-based systems, seem to do exactly what you're asking for. Since you're asking specifically about character backgrounds, I'll skip the part about collaborative game-world creation, which is also present in these games, and skip straight to the characters.
Chapter 3: Character Creation (FC30) opens with the header "Character Creation Is Play." One of the points they make is:
Character creation in Fate is
collaborative. As with game creation,
character creation is best done as a
group activity. Doing all of this together
builds a strong foundation of communication
between the players and GM,
and this process has a number of ways
to establish connections between the
characters and the setting.
The way this happens is through a series of phases. In Fate Core, there are three of these phases, which they call The Phase Trio, and each of them involves creating a new "aspect" for your character. (Note: In Fate, character aspects are short narrative hooks that describe your character and are used to justify your expenditure of Fate Points to create a mechanical bonus or give you an extra bit of narrative control. They can also earn you Fate Points, by complicating your character's life).
The three phases in Fate Core Character Creation are as follows:
- Phase One: Your Adventure
The first phase is your character’s first
true adventure—his first book, episode,
case, movie, whatever—starring him.
You need to think up
and write down the basic
details of this story for the
phase’s summary. The story
doesn’t need to have a lot
of detail—in fact, a pair
of sentences works pretty
well—because your fellow
players will add in their own
details to this past adventure
in the next two phases (as
you will to theirs).
- Phase Two: Crossing Paths
In the next two phases, you’ll tie the group together by having other characters
contribute a minor, supporting role in your adventure, and vice versa.
Once everyone has their adventure written down... you’re ready for phase two.
You can pass to the left or right, or shuffle the stack and hand them out
randomly... However you decide to do it, every player should now be
holding someone else’s adventure.
Your character has a supporting role in the story you’re holding, which
you get to come up with right now. Briefly discuss it with the player whose
adventure it is and add a sentence or phrase to the summary to reflect your
character’s supporting role.
- Phase Three: Crossing Paths Again
Once everyone’s done with phase two, you’ll
trade adventures with whatever method you
chose before, so long as everyone has an adventure
that isn’t theirs or the one they just contributed
to. Then you’re ready for phase three,
where you’ll contribute to this second adventure
and determine your next aspect. Follow the
directions from phase two.
Using this system, your character won't necessarily have met every other character (unless there are only three of you), but you will at least be within a few degrees of separation.
Other Fate-based games, such as Diaspora, Dresden Files RPG, and Spirit of the Century have similar collaborative character creation rules. For example, Diaspora's chapter on characters begins with this gem (p.31):
Creating a character uses a process that creates significant interaction in each others' stories. No Diaspora game begins, "You all meet in a space bar," -- how all the characters know each other and even what dirty secrets they share will all be considered as part of character creation.
I believe Diaspora was created before Fate Core, and the rules actually discuss five phases ("growing up", "starting out", "moment of crises", "sidetracked", and "on your own"), with two aspects being created in each phase. Of these, only phases 3 and 4 directly involve other PC's (those to your right and left, respectively).
Does this meet your requirements?
- A method or system for generating group character backgrounds
Yes. You generate character backgrounds by inserting your character as a supporting character in another character's story.
- It should encourage players to generate history together and moments where they've met/helped each other.
Yes. Each player must be involved in two other character's background stories.
- In the end the players should have something in common with each other and good reasons
Yes. Each character now has the common shared experience of the phases they jointly contributed to. The reasoning is as good as the narratives they collaboratively create.
- It doesn't have to be a game, it could just be a methodology.
Yes. It is not a game (as no dice are rolled), but it is a specific methodology.
- It should be doable in a single game session (3-4 hours or so)
Yes. According to (FC30):
Combined with game creation, character
creation can take a full session to
do—this allows everyone to learn about
the world and each other’s characters.
The one term you use that I'm not sure about is "fractal" -- it's not clear to me from your bullet point list of requirements just how you're using the term, or what you're expecting from it (the term refers to self-similarity across multiple scales). However, Fate uses a concept called the "Fate Fractal" (FC270) to be able to view anything in the game world as a character, and thus capable of having it's own aspects, skills, etc... For example, in the game-world creation section (that I passed over) the game world is described as having it's own aspects, much like a character might.
