This is not so much an answer, as a (long) comment to Robin Chapman's answer. Robin writes

I'm not expert on set theory without AC, but those here who are will surely tell us if there are models of ZF with non-equinumerous infinite sets such that $A$ is the union of ${}|B|$ finite sets and *vice versa*.

I've thought about this question, and I have now convinced myself that there is an open problem here.

(There may be a completely different way of approaching this, but) what looks to me to be the natural approach starts by rephrasing the question in the setting of the dual Schroeder-Bernstein theorem, since Robin's condition says that $A$ and $B$ are surjective images of each other, and each map is finite-to-one (at least if the finite sets are pairwise disjoint).

Since Benjamin Miller had worked on questions of this nature, I asked him about this version. He agreed that the expected example of such sets $A$ and $B$ would come from finding countable Borel equivalence relations $F_0 \subseteq F_1 \subseteq F_2$ on some Polish space $X$ of finite index over one another such that $X / F_0$ and $X / F_2$ are Borel isomorphic, but $X / F_0$ and $X / F_1$ are not universally measurably isomorphic.

Once we have this setting, it is standard how, for example, in models of the axiom of determinacy, we get that $A=X/F_0$ and $B=X/F_1$ are the sets we are looking for.

However, Ben mentioned that his guess was that doing this is a bit finer than what rigidity techniques (the main technical tool in these results) can handle currently. Ben asked around to a few experts, and they agreed with him in this regard.

if you're talking about the infinite rank case. – Kevin Buzzard Dec 9 '10 at 22:20equivalentto "every vector space admits a basis". In fact, his proof gives the same result, even if we fix the field. – Andrés Caicedo Dec 9 '10 at 22:38existenceof bases, that every two bases of a vector space (if they exist) have the same size isnotequivalent to choice. – Andrés Caicedo Dec 10 '10 at 7:17