Following @sss89's hint in the comments.
Denoted with $\operatorname{Cl}(a)$ the conjugacy class of $a\in G$, let's consider the natural action of $\operatorname{Aut}(G)$ on $X:=\{\operatorname{Cl}(a), a\in G\}$, namely: $\sigma\cdot \operatorname{Cl}(a):=\operatorname{Cl}(\sigma(a))$. This is indeed an action because:
- good definition: $a'\in \operatorname{Cl}(a)\Rightarrow \sigma\cdot\operatorname{Cl}(a')=\operatorname{Cl}(\sigma(a'))$; now, $\sigma$ is (in particular) a surjective homomorphism, and hence $\operatorname{Cl}(\sigma(a'))=\sigma(\operatorname{Cl}(a'))=\sigma(\operatorname{Cl}(a))=\operatorname{Cl}(\sigma(a))=\sigma\cdot \operatorname{Cl}(a)$, and the map is well-defined;
- by construction, $\operatorname{Cl}(\sigma(a))\in X, \forall\sigma\in\operatorname{Aut}(G),\forall a\in G$;
- $Id_G\cdot \operatorname{Cl}(a)=\operatorname{Cl}(Id_G(a))=\operatorname{Cl}(a), \forall a\in G$;
- $(\sigma\tau)\cdot\operatorname{Cl}(a)=\operatorname{Cl}((\sigma\tau)(a))=\operatorname{Cl}(\sigma(\tau(a))=\sigma\cdot(\operatorname{Cl}(\tau(a)))=\sigma\cdot(\tau\cdot\operatorname{Cl}(a)), \forall \sigma,\tau\in\operatorname{Aut}(G), \forall a\in G$
The point-wise stabilizer under this action is given by:
\begin{alignat}{1}
\operatorname{Stab}(\operatorname{Cl}(a)) &= \{\sigma\in\operatorname{Aut}(G)\mid \operatorname{Cl}(\sigma(a))=\operatorname{Cl}(a)\} \\
&= \{\sigma\in\operatorname{Aut}(G)\mid \sigma(\operatorname{Cl}(a))=\operatorname{Cl}(a)\} \\
\end{alignat}
and the kernel of the equivalent homomorphism $\phi\colon \operatorname{Aut}(G)\to \operatorname{Sym}(X)$ by:
\begin{alignat}{1}
\operatorname{ker}\phi &= \bigcap_{a\in G}\operatorname{Stab}(\operatorname{Cl}(a)) \\
&= \{\sigma\in\operatorname{Aut}(G)\mid \sigma(\operatorname{Cl}(a))=\operatorname{Cl}(a), \forall a\in G\} \\
\end{alignat}
Now, $\operatorname{Inn}(G)=\{\varphi_b,b\in G\}$, where $\varphi_b(g):=b^{-1}gb$, and hence:
\begin{alignat}{1}
\varphi_b(\operatorname{Cl}(a)) &= \{\varphi_b(gag^{-1}), g\in G\} \\
&= \{b^{-1}gag^{-1}b, g\in G\} \\
&= \{(b^{-1}g)a(b^{-1}g)^{-1}, g\in G\} \\
&= \{g'ag'^{-1}, g'\in G\} \\
&= \operatorname{Cl}(a), \forall a\in G \\
\end{alignat}
whence $\varphi_b\in \operatorname{ker}\phi, \forall b\in G$, and finally $\operatorname{Inn}(G)\subseteq \operatorname{ker}\phi$. Conversely, let $\sigma\in \operatorname{ker}\phi$; then, $\sigma(\operatorname{Cl}(a))=\operatorname{Cl}(a), \forall a\in G$; in particular:
\begin{alignat}{1}
\sigma(\operatorname{Cl}(a))\subseteq\operatorname{Cl}(a), \forall a\in G &\Rightarrow \forall g\in G,\exists g'\in G\mid \sigma(gag^{-1})=g'ag'^{-1}, \forall a\in G \\
&\Rightarrow \exists g''\in G\mid \sigma(a)=g''ag''^{-1}, \forall a\in G \\
&\Rightarrow \exists g''\in G\mid \sigma(a)=\varphi_{g''}(a), \forall a\in G \\
&\Rightarrow \exists g''\in G\mid \sigma=\varphi_{g''} \\
&\Rightarrow \sigma\in \operatorname{Inn}(G) \\
&\Rightarrow \operatorname{ker}\phi\subseteq \operatorname{Inn}(G) \\
\end{alignat}
Therefore, by the double inclusion, $\operatorname{Inn}(G)=\operatorname{ker}\phi$.
EDIT. As per the comments hereafter, I made a mistake in the final part of this answer, from "Conversely..." onwards. Therefore, so far the only inclusion $\operatorname{Inn}(G)\subseteq\operatorname{ker}\phi$ is actually proven.
EDIT (Dec 11, 2020)
I think that the inverse inclusion, and hence the claim, holds for the particular class $G=S_n$, as follows.
Each conjugacy class is a certain cycle structure, and then each stabilizer comprises all and only the automorphisms of $S_n$ which preserve a certain cycle structure, whence $\operatorname{Stab}(\operatorname{Cl}(\sigma))\le\operatorname{Inn}(S_n)$, for every $\sigma\in S_n$. But then, $\operatorname{ker}\phi=\bigcap_{\sigma\in S_n}\operatorname{Stab}(\operatorname{Cl}(\sigma))\le\operatorname{Inn}(S_n)$.