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.
Since $A$ is bounded, its outer measure is finite, since
$$\inf\left\{\sum_{j=1}^{+\infty}\lambda(I_j),A\subset\bigcup_{j=1}^{+\infty}I_j\right\}$$
is finite.
Therefore, for each integer $n$, we can find an open set $G_n$ containing $A$ such that $\lambda(G_n)-\lambda^*(A)\leqslant \frac 1{2^n}.$
Let $G:=\bigcap_{n\geqslant 1}G_n$. We can assume WLOG that $\{G_n\}$ is decreasing. Then $$\lambda(G)=\lim_{n\to +\infty}\lambda(G_n)\leqslant \lambda^*(A).$$
Since $\lambda^*(A)\leqslant \lambda(G_n)$ for all $n$, we have that $\lambda^*(A)=\lambda(G)$.
Best Answer
As Umberto P. already hints at, there are no uncountable subsets $E$ of $\Bbb{R}$ consisting only of isolated points; indeed, the intersection of $E$ with each $[-n,n]$ is finite (why?), so that $E$ is countable (why?).
EDIT: As @TonyK points out, the argument above is incorrect. But it is still true that every set consisting solely of isolated points is countable. To see this, note that each $x \in E$ has an (open) neighborhood $U_x$ in $\Bbb{R}$ such that $E \cap U_x$ is finite (in fact, one can choose $U_x$ so that $E \cap U_x = \{x\}$. Now $\Bbb{R}$ is second countable and hence every subset is separable, so that each subset is Lindelöf (see e.g. Prove that a separable metric space is Lindelöf without proving it is second-countable), so that there is a countable subcover $(U_{x_n})_n$. But then $E \subset \bigcup_n [E \cap U_{x_n}]$ is countable, because each $E \cap U_{x_n}$ is finite.
Also note that the definition of Lebesgue measure requires countable covers by intervals, not finite covers (otherwise, $\Bbb{Q}$ would not have measure zero).
An interesting set of positive (but smaller than expected) measure is obtained by
$$ \bigcup B(x_n, 1/2^n), $$
where $(x_n)_n$ is an enumeration of $\Bbb{Q}$.