The solution is the same for both parts. It is possible to find such A, B and C if and only if n is not 2 (mod 4).
Let us begin by showing that abelian groups can be used to solve all the possible cases.
If n is odd, we simply use modular addition as in the original riddle.
If n=2km with k>1 and odd m, let x=(2k-1xk+...+20x1)m+xw, where each xi is in {0,1} for i=1,..., k, and xw is in {0,...,m-1}. Clearly, this characterisation is unique.
Our group product rule will be that a*b=c if and only if, in the characterisation given above, for all i=1,..., k, ai+bi=ci (mod 2), and aw+bw=cw (mod m).
We use A(x)=x, and for B(x) we use the value b such that bw=xw, for all i=1,..., k-1, bi=xi+1, and bk=x1+xk (mod 2).
It is straightforward to verify that C(x)=A(x)*B(x) has no repeating values.
We are now left with proving that for any n that is 2 (mod 4) there is no solution, even when non-abelian groups are allowed.
Consider the following.
Let n=4m+2 and let G={g1,..., gn}. For any g in G, define σg as the permutation that maps each x to the group element g*x.
Given that σg is a permutation of the elements of G, we can speak of the sign of the permutation. Define s(g) to be the sign of σg for every g in G.
Note that if we take any a and b, and any x in G, σa*b(x)=(a*b)*x=a*(b*x)=σa(σb(x))=(σa ○ σb)(x), so σa*b = σa ○ σb.
In particular, because the sign of the composition of two permutations is the product of the two permutations' signs, we have s(a*b)=s(a)s(b), and this indicates that if s(a)=s(b)=+1 then also s(a*b)=+1, so we can define the subgroup H of G as the subgroup whose elements are those g in G for which s(g)=+1.
By Cauchy's theorem, there is a w in G, other than the identity, satisfying that w2=1. This means that σw ○ σw is the identity.
So, σw is an involution. But because w is not the identity, σw has no fixed points. It is therefore the composition of 2m+1 disjoint transpositions.
It follows that s(w)=-1, so w is not in H. Furthermore, for every g in G, g is in H if and only if w*g is not in H, so |H|=|G|/2.
Now, if A(x)*B(x)=C(x), then s(A(x))s(B(x))=s(C(x)).
Taking the product over all x, we reach the contradiction -1*-1=-1, because G has 2m+1 elements for which s is -1, and this is an odd number of elements.
I thank Serge Gautier again for this lovely riddle, as well as Ian Wanless for his help with finding an elegant solution. The solution in the form given here is lifted pretty much directly from Mathematics Stack Exchange, so let me also thank Jack D'Aurizio, who worded it so brilliantly.
The claim of this riddle is, itself, a special case of a much broader theorem known as the Hall-Paige theorem, which posits that no such A, B and C exist for any group of size 2k(2m+1) with k>0 if the group contains a cyclic subgroup (i.e., a group containing only powers of a single x) of size 2k.