Groups where every permutation of the nonidentity elements is an automorphism. Let $G$ be a group where every permutation of the nonidentity elements gives an automorphism of $G$. For now, assume $G$ is finite.
Since automorphisms preserve orders of elements, every nonidentity element must have order $p$, where $p$ is prime. In addition, since automorphisms preserve the center, we have that $G$ is an elementary abelian $p$ group. If $p>2$, and the dimension of $G$ as a vector space over $\mathbb F_p$ exceeds $1$, then we can send $(1, 0)$ and $(2, 0)$ to $(0, 1)$ and $(1, 1)$, which would not be an automorphism. Thus, if $p$ is odd, $G$ is cyclic, but we know that the automorphism group of $C_p$ has size $p-1\neq (p-1)!$ unless $p=2, 3$. So $C_3$ is the only such $G$ that's not a $2$-group.
As for $2$-groups, if the dimension is at least $3$, then we can send $(1, 0, 0)\mapsto(1, 0, 0), (0, 1, 0)\mapsto (0, 1, 0)$, but $(1, 1, 0)\mapsto (0, 0, 1)$, which fails to be an automorphism. Thus, $C_2$ and $V_4$ are the only nontrivial $2$-groups that work.
Thus, the only such finite groups are $C_1, C_2, C_3, V_4$. In fact, I think the above arguments also rule out infinite groups, so these are the only groups where any permutation of the nonidentity elements gives an automorphism. 
 A: The only such groups are indeed the ones you listed: $C_1, C_2, C_3, C_2 \times C_2$. First, note that such a group $G$ must be abelian:
Suppose $x \not \in Z(G)$, and take $g \in G \setminus C_G(x)$. Then $y := gxg^{-1} \ne x$, and also $y \ne g$ (else $gxg^{-1} = g \implies xg^{-1} = e$). Then $x, y, g$ are pairwise distinct, and so are $xg, x, g$ (and none of these equal $e$), so there is an automorphism $\sigma$ sending $x \mapsto xg$, $y \mapsto x$, $g \mapsto g$, so $x = \sigma(y) = \sigma(gxg^{-1}) = g\sigma(x)g^{-1} = g(xg)g^{-1} = gx$, contradiction. 
Now suppose there exists $x \in G$, $|x| > 2$. Then $x, x^2 \ne e$, so there is an automorphism $\sigma$ interchanging $x$ and $x^2$. Then $x = \sigma(x^2) = \sigma(x)^2 = (x^2)^2$, so $x^3 = e$, and $|x| = 3$. Since automorphisms preserve orders, we conclude that every nonidentity element of $G$ has order $3$. Then $G$ abelian $\implies G$ is a vector space over $\mathbb{F}_3$, necessarily of dimension $\le 1$.
The only remaining case is where every element of $G$ has order $2$, but then $G$ is a vector space over $\mathbb{F}_2$, which is necessarily of dimension $\le 2$, by the reasoning in the original post (note that $C_2 \times C_2$ does work, as $\text{Aut}(C_2 \times C_2) = GL_2(\mathbb{F}_2) \cong S_3$ has $6$ elements).
