Consider the following proposed definition:
A set $X$ is countable iff $X=\emptyset$ or there exists $x_0\in X$ and $f:X\to X$ such that:
$\forall P\subset X: [x_0\in P \land \forall x\in P: [f(x) \in P] \implies P=X]$
In other words, a set $X$ is countable iff $X$ is empty or induction holds on $X$.
Note that, by this definition, if $X=\{x_0\}$ then $X$ is countable. The identity function on $X$ would be the required "successor function."
By this definition, the set of natural numbers is trivially countable.
Comments? Is this definition anything new?
We can show that if $X$ satisfies this property, then there is a surjection $g:\mathbb N\rightarrow X$. Thus $X$ is countable in the usual sense. Of course the converse holds, as you already know.
Define $g$ as $g(0)=x_0$ and $g(n+1)=f(g(n)),\forall n\in\mathbb N$. Then by the property in question, the image of $g$ is equal to $X$, so $g$ is surjective.
Hope this helps.