Nice question again :).
I think your argument looks good and is not too hard to make rigorous (depending a little on which embedding you have in mind - if you wanted to send $X$ to some group $G_X$ with underlying set $X$ that is a bit subtle, actually).
The argument that I like the most proves something even slightly stronger - "there is no set of groups which contains a representative from each isomorphism class":
Lemma. Let $S$ be a set of groups. Then there is some group $G$ such that no element of $S$ is isomorphic to $G$.
Proof. Let $X = \bigcup_{H \in S} H$ be the union of all the underlying sets of the elements of $S$ (if you're being more formal and "group" means "tuple of data" to you, this means
$X = \bigcup_{t \in S} \pi_1(t)$). Let $G$ have underlying set $\mathcal P(X)$, the powerset of $X$, and equip $G$ with the symmetric difference operation to make it into a group.
Then for each $H \in S$, note there is a surjection $X \to H$. Since there is no surjection from $X \to \mathcal P(X)$ (by Cantor's theorem), it follows that $H$ does not even surject onto $G$. So certainly they don't biject, and they definitely aren't isomorphic. QED.
By the way, this argument works perfectly well in ZF, with no choice needed!
This argument is really using the fact that there are groups of arbitrarily large cardinality, and that the elements of any set of sets cannot have arbitrarily large cardinality. This will work equally well for pretty much any other algebraic structure you can think of. In this case it's a bit "lucky" that $\mathcal P(X)$ has a natural operation making it into a group. In general you might have to consider "the free structure on a large set", or "the product of a large number of copies of a nontrivial structure" to make big structures. (In fact $\mathcal P(X)$ is an example of the latter - it's the product of $|X|$ many copies of $C_2$).
In some sense there being groups of arbitrarily large cardinality is the only reason this lemma is true - namely, if $K$ is any set, then the collection of isomorphism types of groups which are the same size as some element of $K$ is a set. More precisely, there is a set $S$ of groups, such that every group $G$ that bijects with some set in $K$ is isomorphic to some group in $S$ (this is because the collection of all group operations on a set $X$ is a set). Particularly, if $\kappa$ is a cardinal then there is a set containing representatives for all isomorphism classes of groups of cardinality less than $\kappa$.