I figured out a solution that just takes some basic combinatorics, and doesn't use the axiom of choice at all; I'm surprised no one else posted something similar already.

Assume $X$ is not finite, since we can handle that case easily.

The transpositions in $S_X$ can be distinguished as follows: They are the conjugacy class $T$ consisting of elements of order 2 with the property that the set of products of pairs of elements of $T$ contains no more than one conjugacy class of order 2. To see that no other conjugacy class satisfies this property, observe that for any product $s$ of at least two disjoint transpositions (including possibly infinitely many), one can select a subset of two of them and interchange two of the letters to obtain $s'$ such that $ss'$ is a product of exactly two disjoint transpositions (using the Klein 4 group in $S_4$). If $s$ is a product of exactly 2 or 3 transpositions then we can multiply by a disjoint product of 2 or 3 transpositions to obtain another conjugacy class. If s is a product of 4 or more transpositions, then we can select another two transpositions in s to obtain $s''$ such that $ss''$ is a product of exactly four disjoint transpositions.

Next we aim to characterize letters as equivalence classes of pairs of elements of $T$ which multiply to an element of order 3, so that the pair $\{(a, b), (b, c)\}$ distinguishes $b$. We need to describe the equivalence relation on these pairs. We can express the transposition $(a, c)$ as a conjugate of one element of the pair by the other. Therefore when we have another pair $\{(a', b'), (b', c')\}$, we can express the condition that $\{a, c\}$ is disjoint from $\{a', c'\}$. In this case we say that the two pairs are related if multiplying any two of the four transpositions gives an element of order 3. Then we take the transitive closure of that relation.

So we have constructed a set from the abstract group $S_X$ which is in natural bijection with $X$. Note that the argument distinguishing $T$ works when $|X| \ge 12$, and the argument characterizing the equivalence relation works when $|X| \ge 7$. There's probably a clever way to adapt both arguments for fewer elements; this is just what I came up with. Note that the transpositions cannot be distinguished in $S_6$.