My question is: can this be proven without using the almighty Axiom of Choice?
Here's the idea of my proof using the axiom:
We need an injective function from $B$ in $A$.
Let $e$ be the choice function, $e: P(A) \rightarrow A$.
It's easy to see that $g = e \circ f^{-1}$ is injective.
What you've written requires the axiom of choice, as you say. However, there is a way around it: define a specific $e$!
HINT: You know that $A$ is countable - this means there is a bijection between $A$ and $\mathbb{N}$ (or $A$ is finite, but that case is trivial), so we might as well assume $A=\mathbb{N}$. Now, to each element $b$ of $B$ we associate the set $$X_b=\{a: f(a)=b\};$$ by assumption $X_b$ is nonempty for each $b$.
Do you know a nicely definable way to pick out an element from a nonempty set of natural numbers?
Exercise: generalize this to show that if $A$ is well-orderable, and $f:A\rightarrow B$ is surjective, then $B$ is well-orderable.