You are missing key conditions in the Euclidean Algorithm; you require $0\leq r\lt a$ in the first step, and in general $0\leq r_{i+1}\lt r_i$, and "terminates" means the remainder is $0$. This is what guarantees that the process terminates: you have a strictly decreasing sequence of nonnegative integers, and therefore it must be a finite sequence before you get $r_n = 0$ for some $n$; certainly, no more than $a$ steps, but in fact less than that since you can show that after two steps the remainders drop by at least half.
I'm not in my office, but unless I am much mistaken the fact that the process terminates is in Niven, Zuckerman, and Montgomery's An Introduction to the Theory of Numbers, among others. I'll check tomorrow.
The formula $\sum_{i=0}^n\frac{(-1)^i}{q_i}=\frac{a}{b}$ doesn't work with your notation, since you either don't have $q_0$ or you don't have $q_1$; I suspect you mistyped your "next step", and that you mean mean $b=aq_0 + r_0$, and then $bq_0 = r_0q_1 + r_1$, and more generally $bq_0\cdots q_k = r_kq_{k+1}+r_{k+1}$ (with the restrictions mentioned above on the $r_j$). Moreover, it requires the extra assumption that $a\lt b$ (otherwise, $q_0 = 0$); this is not usually necessary in the Euclidean algorithm, so you need to specify it if you are going to use that formula.
As to a proof: if the remainder is $0$ the result is immediate, since $b=aq$ with all nonzero implies $\frac{1}{q} = \frac{a}{b}$. Assume the formula holds if the algorithm terminates after $k$ steps, and that you have an application with $k+1$ steps. Using the induction hypothesis applied to $bq_0$ and $r_0$ you have that $\sum_{i=0}^{k} \frac{(-1)^i}{q_{i+1}} = \frac{r_0}{bq_0}.$ Replacing $r_0$ with $b-aq_0$ we get $\sum_{i=0}^k \frac{(-1)^i}{q_{i+1}} = \frac{b-aq_0}{bq_0} = \frac{1}{q_0} - \frac{a}{b}.$ Now solving for $\frac{a}{b}$ gives \begin{align*} \frac{a}{b} &= \frac{1}{q_0} - \sum_{i=0}^{k}\frac{(-1)^i}{q_{i+1}} = \frac{1}{q_0} + \sum_{i=0}^k\frac{(-1)^{i+1}}{q_{i+1}}\\ &= \frac{1}{q_0} + \sum_{i=1}^{k+1}\frac{(-1)^i}{q_i} = \sum_{i=0}^{k+1}\frac{(-1)^i}{q_i}, \end{align*} which proves the formula by induction.
As to the addendum: I don't know which version you are thinking of, but I'll wager a proof by induction will work along the same lines as the one above for it.