A set $A$ is said to be infinite if there is a surjection from $A$ to $\mathbb N_0$.
Let $A$ be infinite, and denote by $b$ some set that is not included in $A$. (Such a $b$ exists by the specification axiom). To prove the equivalence
$$A \sim A \bigcup \{b\} \tag{ 1}$$
in elementary set theory, one usually uses the fact that $A$ has a countably infinite subset (whose universal existance depends on some kind of choice).
- Q: But can the equivalence in $(1)$ be proven in some other way, without the axiom of choice? More specifically, in the context of ZF without regularity?
I assume it cannot be done but I am not sure... I am still quite the novice when it comes to axiom of choice considerations, having begun only yesterday. If if it cannot be done, should I expect the impossibility to have an elementary proof? (Again, I think not but am unsure).
No.
The definition you're using is also known as weakly Dedekind-infinite, and the property you are trying to prove is equivalent to Dedekind-infinite.
If there is an infinite Dedekind-finite set, then there is one which is weakly Dedekind-infinite. To see this, note that if $A$ is Dedekind-finite, either it is weakly Dedekind-infinite, or else its power set can be mapped onto $\Bbb N_0$ (by mapping finite sets to their size and infinite sets to $0$).
Now we can use a theorem of Kuratowski that $A$ is weakly Dedekind-infinite if and only if its power set is Dedekind-infinite. Since $A$ was not weakly Dedekind-infinite, its power set is Dedekind-finite, but we also proved that it is weakly Dedekind-infinite.