I know the fact that every set has a free abelian group with basis $S$, (i.e. for any set $S$, free abelian group on $S$ is a group whose elements can be "uniquely" written by $\mathbb Z$-linear combinations of elements on $S$).
If the fact is true for any set $S$, I don't know how any $S$ can be a basis and $\mathbb Z$-linear combinations on $S$ can be "uniquely" expressed.
Let's think about this problem from a lens of linear algebra because I think this concept can get lost in the weeds if you think about from an abstract algebra perspective. I think what you are probably stuck on is an example like this: Let $\mathcal P_2$ be the free group of integer valued polynomials (we are only allowing addition). Then the sets $$S = \{1, x, x^2\} \text{ and } S' = \{1-x, x - x^2, x^2\}$$ both generate $\mathcal P_2$ as a free abelian group. But how can we have the same group generated by two distinct sets? The error in this is that you are imposing more mathematical structure than the theorem assumes.
In linear algebra we can define a vector space $V$ with basis $\mathcal B = \{b_1, b_2, \ldots, b_n\}$. This is called an $n$-dimensional vector space and we can define a rich theory of linear algebraic properties of $V$. But what is the basis $\mathcal B$? From our perspective, it's just a set of distinct symbols which we call a "basis" of $V$.
That's what this theorem is telling you, it's just saying that given a set of symbols $S$, you can make a free algebra (vector space) with that set as a basis. If you think of $S$ and $S'$ as merely sets of symbols rather than elements of $\mathcal P_2$, then you would get two different free groups (but they would be connected by a group isomorphism taking $1 \mapsto 1-x$, $x \mapsto x-x^2$, $x^2 \mapsto x^2$.
Hope this helps.