For the first question, let us consider the following statement:
$x\in\mathbb R$ and $x\ge 0$. It is consistent with this statement that:
- $x=0$,
- $x=1$,
- $x>4301$,
- $x\in (2345235,45237911+\frac{1}{2345235})$
This list can go on indefinitely. Of course if $x=0$ then none of the other options are possible. However if we say that $x>4301$ then the fourth option is still possible.
The same is here. If all sets are measurable then it contradicts the axiom of choice; however the fact that some set is unmeasurable does not imply the axiom of choice since it is possible to contradict the axiom of choice in other ways. It is perfectly possible that the universe of set theory behave "as if it has the axiom of choice" up to some rank which is so much beyond the real numbers that everything you can think of about real numbers is as though the axiom of choice holds; however in the large universe itself there are sets which you cannot well order. Things do not end after the continuum.
That been said, of course the two statements "$\mathbb R$ is countable union of countable sets and "There are non-measurable sets" are incompatible: if $\Bbb R$ is a countable union of countable sets, then there is no meaningful way in which we can have a measure which is both $\sigma$-additive and gives intervals a measure equals to their length; whereas stating that there exists a set which is non-measurable we implicitly state that there is a meaningful way that we can actually measure sets of reals. However this is the meaning of it is consistent relatively to ZF. It means that each of those can exist with the rest of the axioms of ZF without adding contradictions (as we do not know that ZF itself is contradiction-free to begin with.)
As for the second question, of course each set is countable and thus has a bijection with $\mathbb N$. From this the union of finitely many countable sets is also countable.
However in order to say that the union of countably many countable sets is countable one must fix a bijection of each set with $\mathbb N$. This is exactly where the axiom of choice comes into play.
There are models in which a countable union of pairs is not only not countable, but in fact has no countable subset whatsoever!
Assuming the axiom of countable choice we can do the following:
Let $\{A_i\mid i\in\mathbb N\}$ be a countable family of disjoint countable sets. For each $i$ let $F_i$ be the set of injections of $A_i$ into $\mathbb N$. Since we can choose from a countable family, let $f_i\in F_i$.
Now define $f\colon\bigcup A_i\to\mathbb N\times\mathbb N$ defined by: $f(a)= f_i(a)$, this is well defined as there is a unique $i$ such that $a\in A_i$. From Cantor's pairing function we know that $\mathbb N\times\mathbb N$ is countable, and so we are done.
For the first question, note that if we assume Dependent Choice then all $\sigma$-additivity arguments can be carried out perfectly. In such setting using the Caratheodory theorem makes perfect sense, and indeed the Lebesgue measure is the completion of the Borel measure.
It was proved by Solovay that $\mathsf{ZF+DC}$ is consistent with "Every set is Lebesgue measurable", relative to an inaccessible cardinal. This shows that assuming large cardinals are not inconsistent, we cannot prove the existence of a non-measurable set (Vitali sets, Bernstein sets, ultrafilters on $\omega$, etc.) without appealing to more than $\mathsf{ZF+DC}$.
Under the assumption of $\mathsf{DC}$ it is almost immediate that there are only continuum Borel sets, but if we agree to remove this assumption then it is consistent that every set is Borel, where the Borel sets are the sets in the $\sigma$-algebra generated by open intervals with rational endpoints. For example in models where the real numbers are a countable union of countable sets; but not only in such models. Do note that in such bizarre models the Borel measure is no longer $\sigma$-additive.
For sets with Borel codes the proof follows as in the usual proof in $\mathsf{ZFC}$. There are only $2^{\aleph_0}$ possible codes, but there are $2^{2^{\aleph_0}}$ subsets of the Cantor set, all of which are codible-Lebesgue measurable.
Lastly, we have a very good definition for the Lebesgue measure, it is simply the completion of the Borel measure. The Borel measure itself is unique, it is the Haar measure of the additive group of the real numbers. The Lebesgue measure is simply the completion of the Borel measure which is also unique by definition. This is similar to the case where the rational numbers could have two non-isomorphic algebraic closures, but there is always a canonical closure. Even if you can find two ways to complete a measure, "the completion" would usually refer to the definable one (adding all subsets of null sets).
Best Answer
The answer is, you cannot.
It is consistent with ZF that the real numbers are a countable union of countable sets, this implies that every set of reals is Borel and therefore measurable. Of course, in such model it is nearly impossible to develop the analysis we know.
However it is consistent relative to an inaccessible cardinal that there is a model of ZF+DC where all the sets of real numbers are Lebesgue measurable, and DC allows us to do most of classical analysis too.
Non-measurable sets can be generated by free ultrafilters over $\mathbb N$ too, which as remarked is a strictly weaker assumption that the axiom of choice. If there are $\aleph_1$ many real numbers and DC holds then there is an non-measurable set as well, which implies that ZF+DC($\aleph_1$) also implies the existence of non-measurable sets of real numbers - however this is not enough to imply the existence of free ultrafilters over the natural numbers!
Several other ways to generate non-measurable sets of real numbers:
There are several other ways as well, but none are quite close to the full power of the axiom of choice.
One important remark is that we can ensure that the axiom of choice holds for the real numbers as usual, but breaks in many many severe ways much much further in the universe (that is counterexamples will be sets generated much later than the real numbers in the von Neumann hierarchy). This means that the axiom of choice is severely negated - but the real numbers still behave as we know them.
The above constructions and to further read about ways to construct non-measurable sets cf. Horst Herrlich, Axiom of Choice, Lecture Notes in Mathematics v. 1876, Springer-Verlag (2006).