Generally they have multiple soulstones. On my main account, for instance, I have 13 full soulstones and about a dozen frags. I use the frags for long term storage of skills I don't anticipate using, while about half the full stones are storing skills I interchange a lot. The other half of the full stones are, obviously, empty, so I can dump the skill off that I'm trading for. I can totally change a characters template in about 5 minutes, and, as long as the stats are where they need to be for what I want to do, the character can be back in action immediately.

In your situation I would do what Brom suggested, and have a skill mule to dump skills onto for trading between characters.