The answer is negative. Suppose for contradiction that $S$ is such a surface, and let me first assume that it is smooth and projective.
Fix $g\geq 24$. Then the coarse moduli space of genus $g$ curves $M_g$ is of general type (this is due to Harris, Mumford and Eisenbud, see for instance [The Kodaira dimension of the moduli space of curves of genus $\geq 23$]), hence a fortiori not uniruled.
Let $H$ be the Hilbert scheme of smooth curves of genus $g$ in $S$ and let $(H_i)_{i\in I}$ be its irreducible components: the index set $I$ is countable. By hypothesis, the classifying morphism $H\to M_g$ is surjective at the level of $\mathbb{C}$-points. By a Baire category argument, there exists $i\in I$ such that $H_i\to M_g$ is dominant.
Suppose that the natural morphism $H_i\to \operatorname{Pic}(S)$ is constant. Then $H_i$ is an open subset of a linear system on $S$, hence is covered by (open subsets of) rational curves. By our choice of $g$, $H_i\to M_g$ cannot be dominant, which is a contradiction. Thus, $H_i\to \operatorname{Pic}(S)$ cannot be constant, which proves that $\operatorname{Pic}^0(S)$ cannot be trivial. Equivalently, the Albanese variety $A$ of $S$ is not trivial.
Consider the Albanese morphism $a:S\to A$. The curves embedded in $S$ are either contracted by $a$ or have a non-trivial morphism to $A$. Those that are contracted by $a$ form a bounded family, hence have bounded genus. Curves $C$ that have a non-trivial morphism to $A$ are such that there is a non-trivial morphism $\operatorname{Jac}(C)\to A$, but this is impossible if $\operatorname{Jac}(C)$ is simple of dimension $>\dim(A)$. Consequently, a smooth curve with simple jacobian that has high enough genus cannot be embedded in $S$. This concludes because a very general curve of genus $g$ has simple jacobian (there even exist hyperelliptic such curves by [Zarhin, Hyperelliptic jacobians without complex multiplication]).
As pointed out in the comments, the argument needs to be modified if $S$ is non-algebraic or singular. I explain now these additional arguments.
If $S$ is smooth but non-algebraic, we can use the following (probably overkill) variant. We can consider the open space $H$ of the Douady space of $S$ parametrizing smooth connected curves in $S$. It is a countable union of quasiprojective varieties by [Fujiki, Countability of the Douady space of a complex space] and [Fujiki, Projectivity of the space of divisors on a normal compact complex space]. It has an analytic morphism to the analytic space $\operatorname{Pic}(S)$ parametrizing line bundles on $S$ [Grothendieck, Techniques de construction en géométrie analytique IX §3]. The dimension of $\operatorname{Pic}(S)$ is finite equal to $h^1(S,\mathcal{O}_S)$. The dimension of the fibers of $H\to\operatorname{Pic}(S)$ is at most $1$. Indeed, otherwise, we would have a linear system of dimension $>1$ on $S$ consisting generically of smooth connected curves, hence a dominant rational map $S\dashrightarrow\mathbb{P}^2$, showing that $S$ is of algebraic dimension $2$, hence that $S$ is algebraic. It follows that every connected component of $H$ has dimension $\leq h^1(S,\mathcal{O}_S)+1$. Now choose $g$ such that $\dim(M_g)>h^1(S,\mathcal{O}_S)+1$, and let $H_g$ be the union of connected components of $H$ parametrizing genus $g$ curves. A Baire category argument applied to the image of $H_g\to M_g$ shows that there are genus $g$ curves that do not embed in $S$, as wanted.
Finally, if $S$ is singular, consider a desingularization $\tilde{S}\to S$. The hypothesis on S implies that every smooth projective curve may be embedded in $\tilde{S}$, with the exception of at most a finite number of isomorphism classes of curves (namely, the curves that are connected components of the locus over which $\tilde{S}\to S$ is not an isomorphism). The arguments above apply as well in this situation.
