This isn't too different from the proofs that any of the basic function spaces are complete. Indeed suppose that $(\mu_n)_{n \geq 1}$ is Cauchy for $| \cdot |(\Omega)$. Let $A_i \in \mathcal{A}$. Then $$\| \mu_n(A_i) - \mu_m(A_i) \| \leq | \mu_n - \mu_m |(\Omega)$$
so $\mu_n(A_i)$ is a Cauchy sequence in the Banach space $E$ and hence converges to some element of $E$, which we will call $\mu(A_i)$. So we now have a function $\mu: \mathcal{A} \to E$ which is the pointwise limit of the sequence $\mu_n$. It is hence immediate that $\mu$ is finitely additive.
It remains to see that $|\mu|(\Omega) < \infty$ and that $|\mu_n - \mu|(\Omega) \to 0$. Let's prove them in that order. For the first, take arbitrary disjoint $A_1, \dots A_k \in \mathcal{A}$. Since $\mu_n \to \mu$ pointwise, for $n$ large enough $\sum_i \| \mu_n(A_i) - \mu(A_i) \| \leq 1$. Then, we can estimate,
$$\sum_{i=1}^k \|\mu(A_i)\| \leq 1 + \sum_i \|\mu_n(A_i)\| \leq 1 + \sup_n |\mu_n|(\Omega) < \infty$$
since Cauchy sequences are bounded. So taking the $\sup$ on the left hand side gives us that $| \mu |(\Omega) \leq 1 + \sup_n |\mu_n|(\Omega) < \infty$.
Finally, to see that $\mu_n \to \mu$ for your norm, note that for $\varepsilon > 0$ there is an $N$ (independent of our choice of $A_i$) such that for $n,m \geq N$,
$$\sum_i \|\mu_n(A_i) - \mu_m(A_i)\| \leq |\mu_n - \mu_m|(\Omega) \leq \varepsilon$$
Sending $m \to \infty$ on the left hand side and taking the $\sup$ gives for $n \geq N$
$$|\mu_n - \mu|(\Omega) \leq \varepsilon$$
which shows the desired convergence.
This is not true in general.
Notation: for each $n$, we make a partition $\{B_n^j\}_{j=1}^m $ of $E_0$ into $m$ cells, where $B_n^j$ is the jth cell in the nth partition.
Let $E_0=[0,1]$ and let $\mu$ be the Lebesgue measure on $\mathbb{R}$. Let $f$ be the indicator function for $[1/2,1]$ (or a smooth approximation thereof). At stage $n$, let $B_n^m = [1/2,1]$ and let $B_n^1$ through $B_n^{m-1}$ be some partition of $[0,1/2)$ where each cell has positive measure. Then, $\mu(E_0)^{-1} \int_{E_0} f d\mu = 1/2$, but $$\frac{1}{m} \sum_{j=1}^m \frac{1}{\mu(B_n^j)}\int_{B_n^j}fd\mu=\frac{1}{m}\frac{1}{\mu(B_n^m)}\int_{B_n^m}fd\mu=\frac{1}{m}\longrightarrow 0.$$
Addendum: of course, the reason why you might expect your statement to hold is our intuition from when we divide $E_0$ into cells which are all equal size. But in this case the result holds true at every stage (not just in the limit), since $\mu(B_n^j)=\frac{\mu(E_0)}{m}$ and a convenient cancellation occurs.
However! There is a very similar problem, basically the dual to your stated problem, where you can use martingale techniques. If you have a filtration of partitions (say, countable at each stage) that get coarser and coarser so that in in the limit the partition is just ${\{\emptyset,E_0\}}$, then the conditional expectations with respect to this filtration form a reverse martingale, and one can apply Lévy's Downwards Theorem (14.4 in Williams' Probability with Martingales) to show that this sequence of conditional expectations converges in the limit to the average on $E_0$ (pointwise almost surely - remember, the conditional expectation is understood as a random variable).
This is not precisely the analogue of your question, where you take an unweighted average of the conditional expectations in each cell, but it is nearby enough that I thought it would be worth mentioning.
Best Answer
You are off by a factor of 2: $\| \mu-\nu\| =2\sup_{B\in\mathcal E}|\mu(B)-\nu(B)|$. For this it's important that $\mu $ and $\nu$ are probabilities, so that $\mu(E)-\nu(E)=0$.
Later addition: Let $\lambda=\mu+\nu$ and let $f$ and $g$ be the Radon-Nikodym densities of $\mu$ and $\nu$ with respect to $\lambda$. It's not hard to check that $\|\mu-\nu\|=\int_E|f-g|\,d\lambda$.
First, because $\mu(E)=\nu(E)=1$, if $B\in\mathcal E$ then, $$ 2|\mu(B)-\nu(B)|=|\mu(B)-\nu(B)|+|\mu(B^c)-\nu(B^c)|\le\operatorname{Var}_{\mu-\nu}(E)=\|\mu-\nu\|. $$ This shows that $\|\mu-\nu\|\ge 2\sup_{B\in\mathcal E}|\mu(B)-\nu(B)|$.
For the reverse inequality, $$ \eqalign{ \|\mu-\nu\|&=\int_E|f-g|\,d\lambda\cr &=\int_{\{f>g\}}(f-g)\,d\lambda+\int_{\{f<g\}}(g-f)\,d\lambda\cr &=(\mu-\nu)(\{f>g\})+(\nu-\mu)(\{f<g\})\cr &=|(\mu-\nu)(\{f>g\})|+|(\mu-\nu)(\{f<g\})|\cr &\le 2\sup_{B\in\mathcal E}|\mu(B)-\nu(B)|. } $$