In fact it's an open problem (very likely the oldest open problem in set theory) whether in every model of not AC there is a set with such a paradoxical partition! Here's a nice introduction to the problem by Asaf Karagila http://karagila.org/2014/on-the-partition-principle/