Cleanly swap all occurences of two strings using sed

If StringB and StringA can't appear on the same input line, then you can tell sed to perform the replacement one way, and only try the other way if there were no occurrences of the first searched string.

<file.txt sed -e 's/StringA/StringB/g' -e t -e 's/StringB/StringA/g'

In the general case, I don't think there is an easy method in sed. By the way, note that the specification is ambiguous if StringA and StringB can overlap. Here's a Perl solution, which replaces the leftmost occurrence of either string, and repeats.

<file.txt perl -pe 'BEGIN {%r = ("StringA" => "StringB", "StringB" => "StringA")}
                    s/(StringA|StringB)/$r{$1}/ge'

If you want to stick with POSIX tools, awk is the way to go. Awk doesn't have a primitive for general parametrized replacements, so you need to roll your own.

<file.txt awk '{
    while (match($0, /StringA|StringB/)) {
        printf "%s", substr($0, 1, RSTART-1);
        $0 = substr($0, RSTART);
        printf "%s", /^StringA/ ? "StringB" : "StringA";
        $0 = substr($0, 1+RLENGTH)
    }
    print
}'

Right now, I'm doing something like
...............
The problem with this approach is that it assumes StringC doesn't occur in the file.

I think your approach is fine, you should just use something else instead of a string, something that cannot occur in a line (in the pattern space). The best candidate is the \newline.
Normally, no input line in the pattern space will contain that character so, to swap all occurrences of THIS and THAT in a file, you could run:

sed 's/THIS/\
/g
s/THAT/THIS/g
s/\n/THAT/g' infile

or, if your sed supports \n in the RHS too:

sed 's/THIS/\n/g;s/THAT/THIS/g;s/\n/THAT/g' infile

I think it's perfectly valid to use a "nonce" string to swap two words. If you want a more general solution you can do something like:

sed 's/_/__/g; s/you/x_x/g; s/me/you/g; s/x_x/me/g; s/__/_/g' <<<"say you say me"

That yields

say me say you

Note that you need the two additional substitution here to avoid replacing x_x if you happen to have "x_x" strings. But even that still seems simpler than the awk solution for me.