Your teacher's intuition is the correct one.

First of all, recall that a set $S$ is said to be *Dedekind finite* if there is no bijection between $S$ and any proper subset of $S$. In the early days of forcing Cohen showed that if $ZF$ is consistent, then it is consistent with $ZF$ for there to exist an infinite Dedekind finite set $S$; indeed Cohen's proof shows that $S$ can be arranged to be a collection of real numbers. 

Now the key result that answers your question: It is a theorem of Tarski that if $S$ is infinite but Dedekind finite, then by choosing: 

$B$ := the set of all finite sequences whose members come from A, and 

$A$ := $B$ \ the empty sequence,

then $A$ and $B$ provide a counterexample for your choice-free surjective version of the Cantor-Bernstein theorem, i.e., there is no bijection between $A$ and $B$ [nontrivial], but  there is a injection from $A$ to $B$ [trivial], as well as a surjection from $A$ to $B$ [non-trivial again].

The above solution is plagiarized from Exercise 8 [p.162] of Jech's *The Axiom of Choice* (available as a Dover paperback). The credit to Tarski appears there on p.166.

You may also wish to consult the hints provided for Exercise 2.42 [p.92] of Levy's *Basic Set Theory*, another excellent text republsihed by Dover.