Every finite measure on a topological space is outer regular if and only if it is inner regular, so compactness would be sufficient (and every finite measure on metric space is automatically both inner and outer regular). Another sufficient condition is that the space is the union of an increasing sequence of compact sets, which covers the case of $\mathbb{R}^n$.
One can look this up in: Aliprantis & Border 2006, "Infinite Dimensional Analysis" in section 12.1.
Edit: Lurker has pointed out that aliprantis and Border use the weaker notion of inner regularity of apprximating sets from below by closed sets. What is called inner regularity here, they call tightness. It is automatic for finite measures on Polish spaces but not all metric spaces.
For a general topological space, these definitions are not equivalent.
The following counterexample is essentially Example 7.1.6 in Bogachev's Measure Theory. Let $X$ be a Vitali set of outer measure $1$ in $[0,1]$, such that $X$ is not Lebesgue measurable (and in particular does not have Lebesgue measure zero), but every Lebesgue measurable subset of $X$ does have Lebesgue measure zero. JDH explains how to construct such a Vitali set in this question. Equip $X$ with its subspace topology. (In fact, $X$ is a separable metric space, though it is not completely metrizable.) Then the Borel sets in $X$ are of the form $A \cap X$, where $A$ is Borel in $[0,1]$. For such $A \cap X$, define a measure $\mu$ by $\mu(A \cap X) = m(A)$, where $A$ is Borel in $[0,1]$ and $m$ is Lebesgue measure. It's simple to verify that $\mu$ is a countably additive Borel measure on $X$, with $\mu(X) = 1$. Furthermore, $\mu$ is regular in the sense of your second definition: for a Borel set $A \cap X$ as above, since $A$ is Borel in $[0,1]$ and $m$ is regular, for each $\epsilon$ there are sets $C,U \subset [0,1]$ which are respectively closed and open in $[0,1]$, $C \subset A \subset U$, and $m(U \setminus C) < \epsilon$. But then we have that $C \cap X, C \cap U$ are respectively closed and open in $X$, $C \cap X \subset A \cap X \subset U \cap X$, and $$\mu((U \cap X) \setminus (C \cap X)) = \mu((U \setminus C) \cap X) = m(U \setminus C) < \epsilon.$$
On the other hand, $\mu$ is not regular in the sense of your first definition. If $K \subset X$ is compact, then it is also compact in $[0,1]$ and in particular is Lebesgue measurable, so must have $m(K) = 0$. Then $\mu(K) = 0$ as well. In particular, we cannot approximate $X$ (or any other set of positive $\mu$ measure) from below by compact sets.
If your topological space is Polish, then these two definitions are equivalent, and in fact every finite Borel measure on such a space satisfies both. This is Theorem 7.1.7 in Bogachev.
Best Answer
Take $A=\{0\}\subseteq \Bbb R$. For every open set $G$ containing $A$ there exists an $\varepsilon>0$ such that $]-\varepsilon, \varepsilon[\subseteq G$. This open interval contains infinitely many $\frac 1 n$. Thus $\mu(G)\geq \mu(]-\varepsilon,\varepsilon[) = \infty$. But $\mu(A)=0$. This shows that $\mu$ is not outer regular.