The general notion at work here is the completion of a measure.
$\newcommand{\R}{\mathbb{R}} \newcommand{\B}{\mathcal{B}}$
Let's write $\B$ for the Borel $\sigma$-algebra on $\R$. If $\mu$ is a positive Borel measure on $\R$ (i.e. a countably additive set function $\mu : \B \to [0,\infty]$), let $\B_\mu$ be the $\sigma$-algebra generated by $\B$ together with the sets $\{A \subset B : B \in \B, \mu(B) = 0\}$ (i.e. throw in all subsets of sets with measure zero). This is called "completing $\B$ with respect to $\mu$", and of course $\mu$ has a natural extension to $\B_\mu$. When we take $\mu$ to be Lebesgue measure $m$, $\B_m$ is precisely the Lebesgue $\sigma$-algebra.
In this notation, I think your questions are as follows:
Is $\B_m \subset \B_\mu$ for every $\mu$?
If not, is there a measure $\mu$ with $\B_\mu = \B$?
For 1, the answer is no. As you suspect, the Cantor measure $\mu_C$ is a counterexample. If $C$ is the Cantor set and $f : C\to [0,1]$ is the Cantor function, then we can write $\mu_C(B) = m(f(B))$. If $A \notin \B_m$ is a non-Lebesgue measurable set, then $f^{-1}(A) \notin \B_{\mu_C}$. But $f^{-1}(A) \subset C$ and $m(C) = 0$, so $f^{-1}(A) \in \B_m$.
For the second question, the answer is yes, sort of. One example is counting measure $\mu$ which assigns measure 1 to every point (hence measure $\infty$ to every infinite set). Here the only set of measure 0 is the empty set, which is already in $\B$, so $\B_\mu = \B$. Another example is a measure which assigns measure 0 to every countable (i.e. finite or countably infinite) set, and measure $\infty$ to every uncountable set. Now the measure zero sets are all countable, hence so are all their subsets, but all countable sets are already Borel.
Note these are not Lebesgue-Stieltjes measures, because they give infinite measure to every nontrivial interval.
In fact, suppose $\mu$ is a measure such that $\B_\mu = \B$. Then I claim every uncountable Borel set $B$ has $\mu(B) = \infty$. Suppose $B$ is an uncountable Borel set. It is known that such $B$ must have a subset $A$ which is not Borel. If $\mu(B) = 0$, then $A \in \B_\mu \backslash \B$, which we want to avoid. So we have to have $\mu(B) > 0$. On the other hand, it is also known that an uncountable Borel set can be written as an uncountable disjoint union of uncountable Borel sets. Each of these must have nonzero measure, so this forces $\mu(B) = \infty$. In particular $\mu$ is not Lebesgue-Stieltjes.
So in fact, any Lebesgue-Stieltjes measure has measure-zero sets with non-Borel subsets, and hence can be properly extended by taking the completion.
A closely related idea is that of universally measurable sets, which are those sets $B$ which are in $\B_\mu$ for every finite (or, equivalently, every $\sigma$-finite) measure $\mu$. There do exist universally measurable sets which are not Borel. On the other hand, the above example with Cantor measure shows that there are Lebesgue measurable sets which are not universally measurable.
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 Cantor function [ see https://en.wikipedia.org/wiki/Cantor_function ] is an increasing continuous function $F: \mathbb R \to \mathbb R$ such that $F'(x)=0$ a.e. (w.r.t. Lebesgue measure), $ F(-\infty )=0$ and $F(\infty)=1$. There is a Borel probability measure $\mu $ on $\mathbb R$ such that $\mu (-\infty, x]=F(x)$ for all $x \in \mathbb R$. This measure satisfies your requirements.