So would I. I think it's wrong; I'm pretty sure that the Hausdorff paradox, which is kinda-sorta the equivalent on the sphere, requires some Choice. But maybe I'm confused.
On the other hand, you don't need any Choice for the Sierpinski-Mazuriewicz paradox, which says that there's a subset A of the plane, which can be written as the disjoint union of two "smaller" subsets B and C, but where A, B, and C are all congruent. (But A is countable, so this isn't nearly as startling as Banach-Tarski.) Specifically, let T be translation by (1,0), and let R be rotation about the origin by 1 radian; then let A be the set of points you can get from (0,0) by applying some sequence of T and R, let B consist of the points where the last operation in the sequence was T rather than R, and let C be everything else. Then B = T(A) and C = R(A). (The key point here is that it turns out that the sequence of Ts and Rs is unique, so that B is well-defined.)