Changing Nations (WOTG)

If you wish to sever ties with one nation to ally with another, simply talk to the NPC in the respective nation you wish to join (such as Adelbrecht in Bastok Markets (S)). They will allow you to join after completing the first nation quest. {You can't complete the quest for a nation if you have allied with a different nation. (If you have allied with San'dOria, then you can't get the Blue Recommendation Letter or Green Recommendation Letter. Aldelbrecht will not allow you to complete the quest for Bastok.)}
You do not have to sever ties with one nation in order to complete the quests of another. As long as you complete the first quest and join one nation's respective military, you can start the 2nd and 3rd quests of another nation.
Once you complete all the quests from each nation, you can still switch allegiance afterwards if you like. Simply talk to the NPC in the nation you want to rejoin (Adelbrecht For Bastok, Mainchelite For San d'Oria, or Mhoti Pyiahrs For Windurst) and they'll tell you what to do. For instance, you complete San d'Oria's quests, then Windurst's, then you complete Bastok last and stay allied with Bastok. Then, if you want to rejoin San d'Oria (as an example), just talk to Mainchelite. You cannot switch allegiance if you are partway through doing the initiation quest for another nation; go back and finish that quest, then switch allegiance. Switching allegiances is free if you have never been allied with the nation you are switching to in the past, but if you were allied with them at some point previously, it will cost you 300 Allied Notes and your top two Campaign Medals (if you have any).

I have Snakes on the Plain active, this matters? D: