Assuming the usual consistency caveats, the paradox is no longer a theorem of ZF+DC, but its complement isn't either. So in that case the analogue to the fifth postulate is even stronger, as there are both models in which you get the counterintuitive results of unmeasurable sets and those in which you don't, and the axioms are not strong enough to distinguish the two.
In ZF+DC is it true that measures satisfy the desirable properties mentioned by Colin? I think the sticking point is isometry invariance. Are there measures in ZF+DC of R^3 that are finitely (countably?) additive and isometry invariant?
