As other answers point out, yes, one needs choice. The popular/natural examples of models of ZF+DC where all sets of reals are measurable are models of determinacy, and Solovay's model. They are related in deep ways, actually, through large cardinals. (Under enough large cardinals, $L({\mathbb R})$ of $V$ is a model of determinacy and (something stronger than) elementarily equivalent to a Solovay model.)

An interesting question that this does not settle, is how much choice is required to produce a non-Lebesgue measurable set. It is enough to have a well-ordering of ${\mathbb R}$, by Vitali's construction. But this is too much: The existence of a non-principal ultrafilter on $\omega$ is not enough to well-order the reals, but suffices to give non-measurable sets.

In a slightly different direction, Matt Foreman and Friedrich Wehrung showed a while ago that an appropriate instance of the Hahn-Banach theorem suffices as well. (This is in "The Hahn-Banach theorem implies the existence of a non-Lebesgue measurable set", Fund. Math. 138 (1991), no. 1, 13--19.) Actually, Hahn-Banach can be understood as a choice principle in its own right. Unfortunately, I do not know any references for this in English, but see Xavier Caicedo-Germán Enciso. "El teorema de Hahn-Banach como principio de eleccion", Revista de la Academia Colombiana de Ciencias Vol. 28 (106) (2004), 11-20. For example, from the abstract:

The Hahn–Banach theorem implies the axiom of choice for families of closed convex sets in reflexive spaces and for more general families of convex sets in locally convex spaces.