I've toyed with the idea of creating "Story patches" that follow one specific character like FFIV follows solely Cecil.
Sort of like this...
Rydia
Meet the people of Mist, do a couple of small errands for her Mom, (maybe add a cave for her to go through) watch her Mom command the Mist Dragon and die when the Dragon is defeated. Rydia vs. Cecil and Kain, events happen as normal, no walk to Kaipo, except she does recover there and you proceed to save Rosa by getting to Damcyan, a little more bonding with Tellah along the way, Damcyan-Antlion's Cave-Mt Hobbs is normal. Rydia should get a few fights alongside Rosa in protecting Fabul.
Her story makes a major divergence after being swallowed by Leviathan and brought to the Feymarch. Here she bonds with the various Eidolons and learns to summon Shiva, Ifrit, Ramuh, Titan, and the Mist Dragon through six mini dungeons (along with a story of helping to stop an invasion of the Feymarch by other monsters). Then by now she has aged considerably and is told by Leviathan to assist Cecil who will soon be in danger, and once she makes it out of the Path to the Feymarch (maybe make it so that an evil force is obstructing Leviathan's powers and that evil force is making camp at the base of the Path of the Feymarch) is transported to the front of the Dwarven Castle and quickly gains access, saves the party and... the rest of the game is pretty much normal from there, as would be the case with all five normal characters.
Granted I think Rosa could have an interesting adventure and here's a couple of reasons...
That waterfall basin near Baron always fascinated me and that the basin starts from high in the mountains always made me think that Rosa may have taken a secret path through the waterfall to reach a descending point in the basin and made her way to Damcyan from there. Though her story wouldn't really be much different from that point on.
Kain's however could be Quite different. As you mentioned he is basically lost after Mist. He might even be able to participate in the attack on Damcyan to retrieve the Fire Crystal, then maybe deal with some rebellion in Baron against the King and then off to Fabul to fight Cecil. After that is... tricky. I rather liked that the Dark Elf proved to be an obstacle even to Golbez, I could imagine Kain going into the Magnes Cave and failing to defeat the Dark Elf, I can't think of anything else much creative for him at the moment.
Though I really like the idea of separate character stories.