More pieces than points: the inevitability of paradoxical decomposition

Standard introductions to measure theory use the axiom of Choice to produce non-measurable sets. Sometimes people object to this, on the grounds that it leads to paradoxes like Banach-Tarski. But does dropping Choice allow us to eliminate paradoxical decompositions? We will prove, within ZF, that one of the following must be true: (1) a non-measurable set exists, or (2) there is an equivalence relation on the real numbers with strictly more equivalence classes than there are real numbers.