This is an interesting question, even though it is not well defined. Call a group "good" if it has a "good" bijection between its conjugacy classes and its irreducible complex representations. I agree with Alexander that the definition of a "good" bijection/group should be guided by classes of examples, but I prefer
that a class of bijections/groups should be infinite.
There are families of good metacyclic groups. For example, if $n=2m+1$ is an odd integer, then the dihedral groups $D_{2n}=\langle a,b\mid a^2=b^n=1,\; a^{-1}ba=b^{-1}\rangle$ of order $2n$ are good. The conjugacy classes $\{b^j,b^{-j}\}$, $1\leq j\leq m$, $\{1\}$, and
$\{a,ab,ab^2,\dots,ab^{n-1}\}$ correspond bijectively (I believe this is "good") to the irreducible representations
$\rho_j$, $1\leq j\leq m$, $\sigma_0$, and $\sigma_1$, respectively where $\rho_j(a)=\begin{pmatrix}0&1\\1&0\end{pmatrix}$, $\rho_j(b)=\begin{pmatrix}\zeta_n^j&0\\0&\zeta_n^{-j}\end{pmatrix}$,
$\sigma_k(a)=\begin{pmatrix}(-1)^k\end{pmatrix}$, $\sigma_k(b)=\begin{pmatrix}1\end{pmatrix}$ and $\zeta_n=e^{2\pi i/n}$.
If an infinite family $G_1, G_2,\dots$ of groups is good, then you know a vast amount about each $G_n$ and can likely produce is a formula writing $|G_n|$ as a sum of the squares of the degrees of the irreducible representations. For $D_{2n}$ this is $2n=4m+2=m\times 2^2+2\times 1^2$. If $G_n$ is an extraspecial group of (odd) order $p^{1+2n}$ and exponent $p$, then the formula is $p^{1+2n}=(p-1)\times(p^n)^2+p^{2n}\times 1^2$. Perhaps the existence of such a formula should be part of the elusive definition of "good".
Addition: Yes Alexander, you are correct, the extraspecial groups $G_n$ of order $p^{1+2n}$ and odd exponent $p$ are "good". To describe a "good" bijection I need some notation. Let $f_n\colon V\times V\to\mathbb{F}_p$ be a nondegenerate symplectic form on $V=\mathbb{F}_p^{2n}$. Multiplication in $G_n=V\times \mathbb{F}_p$ is given by $(v_1,\lambda_1)(v_2,\lambda_2)=(v_1+v_2,\lambda_1+\lambda_2+{\frac12}f_n(v_1,v_2))$, or by the matrices you indicate. The conjugacy classes are as follows: the $p$ one-element (central) classes $Z_\lambda:=\{(0,\lambda)\}$, $\lambda\in\mathbb{F}_p$, and the $p^{2n}-1$ classes $C_v:=\{(v,\lambda)\mid \lambda\in\mathbb{F}_p\}$ where $0\neq v\in V$. The irreducible representations are also easy. The trivial degree-1 representation corresponds to class $Z_0$ containing the identity element. The $p^{2n}-1$ nontrivial degree-1 representations correspond to the $p$-element classes $C_v$. The remaining $p-1$ irreducibles of degree $p^n$ correspond to the $p-1$ central conjugacy classes $Z_\lambda$, with $0\neq\lambda\in\mathbb{F}_p$. Fix a maximal totally isotropic subspace $W$ of $V$. By Witt's theorem $|W|=p^n$. Then $A:=W\times\mathbb{F}_p$ is a maximal abelian subgroup of $G_n$ of index $p^n$. Let $\sigma_\lambda$ be the 1-dimensional representation of $A$, with kernel $W$, mapping $(0,1)$ to $e^{2\pi i\lambda/p}$. The induced representations $\rho_\lambda={\rm Ind}_A^{G_n}(\sigma_\lambda)$ are irreducible of degree $p^n$. (A direct calculation shows $\langle\rho_\lambda,\rho_\lambda\rangle=1$.
Choosing a different $f_n$, or a different maximal totally isotropic subspace $W'$, gives equivalent representations $\rho'_\lambda$. The $W$s are permuted by ${\rm Aut}(G_n)$.) This is a "good" bijection, as identifying $V$ with its dual seems allowed.
According to the book "Permutation groups" by Peter Cameron, your first version, concerning maximal subgroups of $S_n$ was announced in 1979 before the announcement of the completion of CFSG, so it did not depend on CFSG at that point.
There is a complication however, because the earliest versions of O'Nan-Scott erroneously omitted the twisted wreath product case, which was pointed out later by Aschbacher. But the twisted wreath products are not maximal in $S_n$ - they are contained in the product type $S_l \wr S_k$ maximals, so I don't think that affects the maximality theorem.
According to Chapter 4 of Dixon and Mortimer's book on Permutation Groups, whihch deals with the O'Nan-Scott Theorem, the only place where the Schreier conjecture is used (Theorem 4.7B of Dixon and Mortimer) is in the analysis of the primitive groups with a regular nonabelian normal subgroup (which is exactly the twisted wreath product case), and I believe that no proof of that result is known that does not use the Schreier Conjecture. So if you want to avoid it, then you just have to leave that case without further information.
I heard Chris Parker from Birmingham give a talk for students on the O'Nan-Scott Theorem a few years ago, and I remember he did address the question of use of CFSG, and I believe it was exactly as I have described here, but you could write to him to check!
Addendum: Just to emphasize the dependence on the Schreier Conjecture, if that conjecture had been false, then it is conceivable that there could be two simple groups $S,T$ with $T \le {\rm Aut}(G)$ but $T \not\le {\rm Inn}(G)$, in which $T$ leaves no nontrivial proper subgroup of $S$ invariant, in which case the semidirect product $S \rtimes T$ acting on the cosets of $T$ would be a primitive permutation group having $S$ as regular normal subgroup.
Best Answer
Bret Benesh and Ben Newton determined all pairs $(m,n)$ such that $S_m$ contains a maximal subgroup isomorphic to $S_n$. They are either $(n+1,n)$ with the obvious inclusion (or mapping $S_5$ into the image of a point stabilizer under the outer automorphism of $S_6$); $(\binom{n}{k},n)$, coming from the action of $S_n$ on the subsets of $k$ elements of $\{1,2,\ldots,n\}$; and $((kr)!/(r!)^k k!, kr)$ with $1\lt k,r$, with $S_{kr}$ acting on the the right cosets of a maximal subgroups of the wreath product $S_k\wr S_r$. This appears in A classification of certain maximal subgroups of symmetric groups, J. Algebra 304 (no. 2) pp. 1108-1113, MR2265507.
Bret later also determined all pairs $(m,n)$ such that $S_m$ has a maximal subgroup isomorphic to $A_n$; such that $A_m$ has a maximal subgroup isomorphic to $S_n$; and such that $A_m$ has a maximal subgroup isomorphic to $A_n$. This appears in the book Computational Group Theory and the Theory of Groups, Contemporary Mathematics 470 (L-C Kappe, R. F. Morse, and me as editors), AMS 2008; the paper is A classification of certain maximal subgroups of alternating groups, pp. 21-26, MR2478411.
As pointed out by Jack, this does exhaust all possible embeddings of $S_n$ into $S_k$ (presumably you are okay with the maps that are not embeddings...)