Constructing an outer measure on a set whose measurable sets are exactly a given sigma algebra on the set.
Second attempt for a counter-example. :-)
Let $X=X_0\times\{1,2\}$ with some uncountable set $X_0$, and let $\mathcal{M}=\{A\times\{1,2\}:~A\subset X_0,~\text{either $A$ or $X_0\setminus A$ is countable.}\}$
Suppose that there is an outer measure $\mu^*$ on $P(X)$ such that $\mathcal{M}$ is precisely the set of $\mu^*$-measurable sets.
Notice that for every $x\in X_0$, the sets $\{(x,1)\},\{(x,2)\}\notin\mathcal{M}$, so these sets are not measurable; therefore $\mu^*\big(\{(x,1)\}\big)>0$, $\mu^*\big(\{(x,2)\}\big)>0$ and $\mu^*\big(\{(x,1),(x,2)\}\big)>0$.
Take some $A_0\subset X_0$ such that both $A_0$ and $X_0\setminus A_0$ are uncountable, and let $A=A_0\times\{1,2\}$. Obviously $A\notin\mathcal{M}$, so $A$ is not measurable. Hence, there is some $B\subset X$ such that $\mu^*(B\cap A)+\mu^*(B\setminus A)>\mu^*(B)$. It follows that $m:=\mu^*(B)$ is finite.
Let $B_0=\{x\in X_0:\text{ $(x,1)\in B$ or $(x,2)\in B$}\}$ be the projection of $B$ on $X_0$. We shall prove that $B_0$ is countable.
Take a positive integer $k$ and arbitrary elements $c_1,\ldots,c_n\in B_0$ such that $\mu^*\big(B\cap\{(c_i,1),(c_i,2)\}\big)>\frac1k$. Let $C=\{c_1,\ldots,c_n\}\times\{1,2\}$; since $\{(c_i,1),(c_i,2)\}$ is measurable, we get $$ m=\mu^*(B) \ge \mu^*(B\cap C)=\sum_{i=1}^n \mu^*\big(B\cap\{(c_i,1),(c_i,2)\}\big)>\frac{n}{k}, $$ so $n<km$. Hence, there are only finitely many elements $c\in B_0$ such that $\mu^*\big(B\cap\{(c_i,1),(c_i,2)\}\big)>\frac1k$.
Since $\mu^*\big(B\cap\{(c,1),(c,2)\}\big)>0$ for all $c\in B_0$, this proves that $B_0$ is countable.
Now we can replace $A$ by $A'=A\cap(B_0\times\{1,2\})\in\mathcal{M}$. Note that $B \cap A = B \cap A'$, so that we get a contradiction by $$ \mu^*(B) < \mu^\ast(B\cap A)+\mu^*(B\setminus A) = \mu^\ast (B\cap A')+\mu^*(B\setminus A') = \mu^*(B). $$