Como señalan otras respuestas, sí, hay que elegir. Los ejemplos populares/naturales de modelos de ZF+DC en los que todos los conjuntos de reales son medibles son los modelos de determinismo y el modelo de Solovay. En realidad, están relacionados de manera profunda, a través de grandes cardinales. (Con cardinales suficientemente grandes, $L({\mathbb R})$ de $V$ es un modelo de determinismo y (algo más fuerte que) elementalmente equivalente a un modelo Solovay).
Una cuestión interesante que esto no resuelve, es cuánta elección se requiere para producir un conjunto medible no-Lebesgue. Basta con tener un buen ordenamiento de ${\mathbb R}$ por la construcción de Vitali. Pero esto es demasiado: La existencia de un ultrafiltro no principal en $\omega$ no es suficiente para ordenar bien los reales, pero basta para dar conjuntos no mensurables.
En una dirección ligeramente distinta, Matt Foreman y Friedrich Wehrung demostraron hace un tiempo que también basta con una instancia apropiada del teorema de Hahn-Banach. (Esto se encuentra en " El teorema de Hahn-Banach implica la existencia de un conjunto medible no Lebesgue ", Fund. Math. 138 (1991), nº 1, 13--19). En realidad, Hahn-Banach puede entenderse como un principio de elección por derecho propio. Desgraciadamente, no conozco ninguna referencia al respecto en español, pero véase 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. Por ejemplo, del resumen:
El teorema de Hahn-Banach implica el axioma de elección para familias de conjuntos convexos cerrados en espacios reflexivos y para familias más generales de conjuntos convexos en espacios localmente convexos.