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).
I found an example in this journal paper. Let $\beta$ be a Bernstein set, i.e. a subset of $\mathbb{R}$ such that both it and its complement intersects every uncountable closed subset of $\mathbb{R}$. (This post describes how to construct such a set using the axiom of choice.) And let $\gamma$ be a dense measure-$0$ $G_\delta$ subset of the fat Cantor set. (This answer describes how to construct such a set.)
Then $\beta\cap\gamma$ is a Lebesgue measurable set which cannot be written as a union of a Borel set and a subset of a measure $0$ $F_\sigma$ set. This is proven in the linked paper.
Best Answer
If $A$ is a Lebesgue measurable set in $\mathbb R^{m}$ which is not a Borel set then $A \times \mathbb R^{n}$ belongs to the product of the Lebesgue $\sigma$ algebras but it is not a Borel set in $\mathbb R^{m+n}$.