Stefan, "low" cardinalities do not change by passing from $L({\mathbb R})$ to $L({\mathbb R})[{\mathcal U}]$, so the answer to the second question is that the existence of a nonprincipal ultrafilter does not imply the existence of a Vitali set.
More precisely: Assume determinacy in $L({\mathbb R})$. Then $2^\omega/E_0$ is a successor cardinal to ${\mathfrak c}$ (This doesn't matter, all we need is that it is strictly larger. That it is a successor is a result of Richard Ketchersid and I in our forthcoming paper on $G_0$-dichotomies, though it was long suspected. It is my understanding that it also follows from unpublished work by Foreman and Magidor).
Force with ${\mathcal P}(\omega)/Fin$ to add a Ramsey ultrafilter, so you are in the model studied by Di Prisco-Todorcevic. (The model was first studied by J.M. Henle, A.R.D. Mathias, and W.H. Woodin, in "A barren extension", in Methods in Mathematical Logic, Lecture Notes in Mathematics 1130, Springer-Verlag, 1985, pages 195-207, where they show for example that no new sets of ordinals are added in this extension.)
In their forthcoming paper on "Borel cardinals and Ramsey ultrafilters" by Ketchersid, Larson, and Zapletal, the question of how the (non-well-ordered) cardinality structure changes by going to this model is studied. I believe there are still many questions left, but one of the problems they have settled is in showing that $2^\omega/E_0$ is still strictly larger than ${\mathfrak c}$. This means we cannot pick representatives of the Vitali classes, of course (if $\sim$ is the Vitali equivalence relation, then ${\mathbb R}/\sim$ and $2^\omega/E_0$ are ``Borel isomorphic''), or else we would have that $2^\omega/E_0$ and $2^\omega$ have the same size by Schroeder-Bernstein.
The answer to your first question is yes, and the answer to your second question is no, under any of the multiple definitions of "measurable" in choiceless contexts.
We will prove a theorem relating various measure-theoretic consequences of countable choice.
(ZF) The following are equivalent. Note that (1)-(6) are about the algebra of subsets of $[0,1]$ which satisfy $\lambda^*(X)+\lambda^*([0,1] \setminus X)=1$ while (7) refers to the algebra of subsets of $\mathbb{R}$ which satisfy $\lambda^*([-n, n] \cap X) + \lambda^*([-n, n] \setminus X) = 2n$ for all $n.$
- Lebesgue measure is $\sigma$-additive.
- A countable union of measurable sets is measurable.
- A countable union of null sets is measurable.
- A countable union of null sets is null.
- Every null set is contained in a null $G_{\delta}$ set.
- For every measurable set $X,$ there is an $F_{\sigma}$ set $A$ and a $G_{\delta}$ set $B$ such that $A \subset X \subset B$ and $B \setminus A$ is null.
- Any of the above but for measurable subsets of $\mathbb{R}.$
Proof:
(1) $\rightarrow$ (2) Clear.
(2) $\rightarrow$ (3) Clear.
(3) $\rightarrow$ (4) Suppose towards contradiction $X_i$ are null sets with $\lambda(\bigcup_{i<\omega} X_i)>0.$ Let $Y_i = \{x+\frac{m}{2^i}: m < 2^i, \exists j < i (x \in X_j)\}$ (note that addition is mod 1) and $Z_i = Y_i \setminus Y_{i-1}.$ In particular, the $Z_i$ are disjoint null sets whose union has positive measure and is closed under translation by dyadic rationals.
For $A \subset \omega,$ let $H_A=\bigcup_{n \in A} Z_n.$ By (3), each $H_A$ is measurable. We will show that for every $A \subset \omega,$ either $H_A$ or $H_{\omega \setminus A}$ has measure 1.
Suppose $H_A$ has positive measure (otherwise $H_{\omega \setminus A}$ has positive measure). Fix $\epsilon>0.$ By Lebesgue density theorem, there is some interval $I$ of length $\frac{1}{2^n}$ such that $\lambda(H_A \cap I) > \frac{1-\epsilon}{2^n}.$ Clearly $H_{A \setminus (n+1)}$ also satisfies this inequality, and is furthermore closed under translation by $\frac{1}{2^n}.$ Thus, $\lambda(H_A) = \lambda(H_{A \setminus (n+1)}) > 1-\epsilon,$ so $\lambda(H_A)=1.$
Since $H_{\omega}$ has measure 1, we see that $[0,1]$ is a countable union of null sets. By (3), every subset of $[0,1]$ is measurable. However, $\{A \subset \omega: H_A \text{ is measure 1} \}$ is a non-principal ultrafilter, so there is a nonmeasurable subset of $[0,1],$ contradiction.
(4) $\rightarrow$ (1) Let $X_i$ be measurable sets. Let $U_i$ enumerate the basic open sets. Define $S_n \subset \omega$ recursively by having $i \in S_n$ iff there is $j$ such that $\lambda(U_i \cap X_j \setminus \bigcup_{k<i, k \in S_n} U_k) > \frac{n}{n+1} \lambda(U_i).$ Let $V_n = \bigcup_{i \in S_n} U_i.$ Then $V:=\bigcap_{n < \omega} V_n$ is a $G_{\delta}$ set such that $\lambda(V)=\sup_{n<\omega} \lambda(\bigcup_{i < n} X_i)$ and $V \triangle \bigcup_{i<\omega} X_i$ is null.
(4) $\rightarrow$ (5) Let $X$ be null. By (4) we can assume $X$ is closed under translation by rational numbers. Let $U$ be an open cover of $X$ of measure less than $\frac{1}{2}.$ We can canonically cover $X \cap [0, \frac{1}{n}]$ with an open set of measure $\frac{1}{2n}$ by considering the least $m$ such that $\lambda(U \cap [\frac{m}{n}, \frac{m+1}{n}])<\frac{1}{2n}.$ We can thus recursively construct open covers of $X$ of measure less than $\frac{1}{2^n}.$
(5) $\rightarrow$ (6) Similarly to in (4) $\rightarrow$ (1), there is a $G_{\delta}$ set $B_1$ with null symmetric difference from $X.$ Let $B_2$ be a null $G_{\delta}$ set containing $X \setminus B_1.$ Then $B:=B_1 \cup B_2$ is a $G_{\delta}$ set with $X \subset B$ and $B \setminus X$ null. We can similarly construct such a $B'$ for $[0, 1] \setminus X$ and set $A = [0, 1] \setminus B'.$
(6) $\rightarrow$ (4) Let $X_i$ be null sets. Let $X=\bigcup_{i<\omega} X_i.$ Consider $Y = \{2^{-i-1}(1+x): x \in X_i\}.$ It is easy to see $Y$ is null, and thus contained in some null $G_{\delta}$ set $Y'.$ Let $U_n$ be a sequence of open sets covering $Y,$ each satisfying $\lambda(U_n)<\frac{1}{n}.$
Fix $\epsilon>0$ and $i<\omega.$ Let $n$ be least such that $\frac{1}{2^n}<\frac{\epsilon}{4^{i+1}}.$ Then $X_i$ is covered by a translation of $U_n$ scaled up by $2^{i+1},$ which has measure less than $\frac{\epsilon}{2^{i+1}}.$ Applying this construction to all $i,$ we get a cover of $X$ of measure less than $\epsilon.$ Thus, $X$ is null.
(7) Finally, it is routine to verify that assertions (1)-(6) collectively prove their generalizations to $\mathbb{R}.$ E.g., one could verify $\frac{1}{x}$ on $(0, \infty)$ sends null sets to null sets and measurable sets to measurable sets
using the fact that it's Lipschitz on each $[2^{-n}, 2^n]$ and that $\frac{1}{x}$ sends $G_{\delta}$ null sets to $G_{\delta}$ null sets. $\square$
Thus, $\text{M}_{\omega}$ fails in any model of ZF + "$\mathbb{R}$ is a countable union of countable sets" since this theory negates (1), providing an affirmative answer to question 1. As for question 2, if $\neg \text{BNM}$ holds, then we immediately have (2), so every subset of $\mathbb{R}$ is measurable. In particular, all interpretations of "all sets are measurable" are equivalent.
Best Answer
See the Prime ideal theorem.
The existence of ultrafilters on every Boolean algebra (which implies non-principal ultrafilters on ω, since these come from ultrafilters on the Boolean algebra P(ω)/Fin) is a set-theoretic principle that follows from AC and is not provable in ZF (if ZF is consistent), but which does not imply full AC. Thus, it is an intermediate weaker choice principle.
Your statement about ultrafilters on ω appears to be even weaker, since it is such a special case of the Prime Ideal Theorem.
Nevertheless, I believe that the method of forcing shows that it is consistent with ZF that there are no non-principal ultrafilters on ω. I believe that some of the standard models of ¬AC, built by using symmetric names for adding Cohen reals, have DC, and hence also ACω, but still have no nonprincipal ultrafilters on ω. In this case, neither DC nor ACω would imply the existence of such ultrafilters.
I'm less sure about finding models that have ultrafilters on ω, but not on all Boolean algebras. But I believe that this is likely the case. These models would show that your principle is strictly weaker even than the Prime Ideal Theorem.