Is it possible to define countability without referring the natural numbers? Cantor defined countable sets as

A set is countable if there exists an injective function from the set to the set of natural numbers.

Still today countability is almost always defined in Cantor's words. Are the natural numbers really necessary to define countability. Most mathematicians admit that set theory is still a rich subject to study without getting into the conception of numbers. And I believe that the notion of countability is more fundamental than the set of natural numbers itself. Hence I wonder is it possible to define countability without referring the natural numbers?
Let $A$ be a set and let $S:A\rightarrow A$ be a successor function which is characterised by the following properties. 


*

*Two different elements in $A$ can not have same successor. 

*The successor of an element should not be its ancestor.
Shall I define countable sets as below?

A set is countable if there exists a successor function as characterised above.

 A: Yes. You can. Depending on the available tools.

*

*A set $A$ is countable if and only if whenever $B\subseteq A$ and $|B|<|A|$, then $B$ is finite. If you want countable to refer only to infinite sets, then you can also add that there is a proper subset of $A$ which is equipotent with $A$.
Now, you might argue that finiteness depend on the natural numbers, but don't worry, Tarski got you covered: $X$ is finite if and only if the partial order $(\mathcal P(X),\subseteq)$ is well-founded.


*A set $A$ is countable if and only if it can be linearly ordered such that every proper initial segment is finite. Again, if you are only interested in infinite sets, add the requirement that there is no maximal element.
A: 
A set $S$ is countable iff $S$ injects into every set $T$ that non-surjectively injects into $T$.

Basically, $S$ is countable iff $S$ is no larger than every infinite set.

A set is countable if there exists a successor function as characterised above.

Henning Makholm already explained why this is wrong, but I wish to point out that it is because you did not get an equivalence. If a set is countable then there exists a successor function like you said, but the converse does not hold.
A: Two sets are equipotent iff there is a bijection between them.
A set is finite iff it admits a total ordering in which every nonempty subset has a least element and a greatest element; otherwise it is infinite.
(Alternatively, a set $A$ is infinite iff the set $\mathcal P(\mathcal P(A))$ is equipotent to a proper subset of itself.)
A set is countable (finite or countably infinite) iff all of its infinite subsets are equipotent.
A: No that does not work. Even if you add a condition that there is an element (representing $0$) that is not the successor of anything), the definition would still claim that, for example
$$ (\mathbb R \setminus \mathbb Z) \cup \mathbb N $$
is countable, just by defining "successor" as the usual $x\mapsto x+1$.

What modern (since the early 1900s) set theory actually does does not depend directly on the natural numbers:


*

*A set $A$ is called inductive iff $\varnothing \in x$, and for every $x\in A$ it holds that $x\cup\{x\}\in A$ too.


*There's an explicit axiom of set theory promising that at least one inductive set exists.


*The intersection of all inductive sets is called $\omega$.


*A set is called "countable" if it is in bijective correspondence with (some subset of) $\omega$.

It turns out that the elements of $\omega$ are good candidates for representing the natural numbers within set theory, so usually we end up defining $\mathbb N$ to be an alternative name for $\omega$ -- but countability does not actually depend of the number-ness of $\omega$'s elements. (It doesn't care about arithmetic, for example).
A: If you're working in a constructive theory, then the concepts of denumerable (countable) and recursively enumerable (semidecidable) precisely coincide, so you can avoid direct reference to the natural numbers that way.
Certainly, if a set is recursively (computably) enumerable, then it is countable. A simple counting algorithm that outputs the members of the set can be used to demonstrate this fact. This works even in a classical setting, of course.
Now, if a set is countable, then the construction (in some formal system) of its characteristic function provides an algorithm for deciding the set, by the Curry-Howard correspondence. Thus the set is recursive. (The Curry-Howard correspondence, by virtue of being an isomorphism, can be used to show the converse too, but I wanted to show that the converse holds even in a classical theory, as per above.)
