GarmGarf, that sounds pretty clever. I'll have to think about it :).

TRY THIS:
write the story in the first person from a secondary character point of view , a character that "witnesses" both main characters.

I've written a quite long story some time ago called : "The factory of dreams" where there are four main characters, and each of them tells the same story in first person and it came out very nice (as other people appreciated it).

so build the story told by a secondary (dummy) character in first person.
Then approach the game from the third person as the secondary character tells about the others. It's better like this, because if you only have one narrator that is a witness of the storyline, he can be in only one place once,if you build it directly from the third person view you will tend to create an omniscient narrator and parallel plans, witch you do not want, as the player is just one, and can only be in one place at once.