Measure theory without the Axiom of Choice (not even countable choice) is discussed in <a href="http://www.essex.ac.uk/maths/staff/fremlin/mt.htm">Fremlin, Measure Theory</a>, Volume 5, Chapter 56. This is freely available online. Thanks to MO and ex-falso-quodlibet for making me aware of this extensive text in <a href="http://mathoverflow.net/questions/11591/suggestions-for-a-good-measure-theory-book/11600#11600">this answer</a>.

He mentions Feferman & Levy's result that it is consistent that the reals are a countable union of countable sets, as per Andres' answer. This makes the standard definition of Borel sets unhelpful, as everything is Borel.
However, it is still possible to do analysis and measure theory without choice. You just need the right definitions. Fremlin discusses *codable Borel sets*. Unions and intersections of 'codable sequences' of codable Borel sets are themselves codable Borel sets. The basic idea is to represent exactly how a set is built up in terms of successive sequences of unions and set-complements, starting from an enumeration of a base for the topology. This done via countable tree structures, which define a construction of subsets of R (or any Polish space) by applying countable unions of complements as you step along the tree. This definition uses a countable transfinite induction to construct the map from trees to codable Borel sets. An important point being:

> In the presence of countable choice, codable Borel sets = Borel sets.

I see that Andres & Joel mention this as a theorem in their answers. However, 
it is not true without countable choice. The union of a sequence of codable Borel sets does not have to be Borel, so even if the reals could be written as a countable union of countable sets it does not follow that all subsets are codable Borel. However, given a sequence of codable Borel sets with a specified choice of codings, their union is codable Borel. Without countable choice, it makes sense to work with codable Borel sets instead of the standard Borel sets. Then, many standard results carry across to the situation without countable choice.
E.g., a set is codable Borel if and only both it and its complement are analytic sets (continuous images of closed subsets of $\mathbb{N}^\mathbb{N}$).