Vitali's counter-example for the existence of a non-trivial measure requires the Axiom of Choice. But not assuming the Axiom of Choice then prohibits choosing and actually using that measure. There is more to it than just Banach-Tarski.