Is there a way to describe all finite groups $G$ such that $\operatorname{Aut}(G) \cong S_3$?
Two groups that definitely satisfy that condition are $S_3$ itself (as it is a complete group) and $\mathbb{Z}_2 \times \mathbb{Z}_2$ (as $S_3$ is isomorphic to $GL(2, 2)$).
I have read somewhere that those two groups are the only two groups that satisfy that condition. There was no proof of this statement given, however, so I do not know whether it is true or false (and if it is true, it would be interesting to know the proof).
Any help will be appreciated.
Partial answer: look at $G/Z(G)$, the subgroup of inner automorphisms of $Aut(G)$. This group has order $1,2,3$ or $6$. The first three cases all lead to $G$ being abelian (we use the well-known: if $G/Z(G)$ is cyclic, then $G$ is abelian). The only abelian case is $G \cong V_4$ as you mentioned.
Hence we can focus on $G/Z(G) \cong S_3$. Indeed, as you mentioned $G=S_3$ is an example. So we are now talking about central extensions of $S_3$. These are "measured" by the so-called Schur Multiplier (and really is a cohomology group, see here.) We can infer that $G' \cong A_3$. This last fact requires some more sophistication: there is a theorem that says: if $G$ has an abelian Sylow $p$-subgroup, then $p$ does not divide $|G' \cap Z(G)|$. The proof of this requires transfer (which is connected to cohomology theory) or character theory.