A sequence is convergent if and only if it has a limit, so no, Cauchy sequences are not necessarily convergent in non-complete spaces. However, there is the notion of a completion. Given a metric space $X$ a completion of $X$ is a complete metric space $\hat X$ in which $X$ is densely and isometrically imbedded. It turns out every metric space has a unique (up to isometric bijection) completion. So in this sense, a non-convergent Cauchy sequence in $X$ will converge in $\hat X$. This is non-trivial however and you are best not to use phrases such as "converges but in another space".
There is a notational issue here. You need to show that a Cauchy sequence of elements of $c_0$ converges to an element of $c_0$. It might help to refer to an element of $c_0$ as $x$, and then address a specific element of the sequence as $x(k)$.
So suppose you have $x_n \in c_0$ such that $x_n$ is Cauchy with the distance
given above.
For each $k$, you have $|x_n(k)-x_m(k)| \le d(x_n,x_m)$, so there is some $x(k)$
such that $x_n(k) \to x(k)$. This is the candidate sequence.
Now you must show that $x \in c_0$ and $d(x,x_n) \to 0$.
Let $\epsilon>0$, choose $N$ such that if $m,n \ge N$ then
$d(x_n,x_m) < { 1\over 3} \epsilon$. Now choose $K$ such that
if $k \ge K$, then $|x_N(k) | < { 1\over 3} \epsilon$. Then, for $k \ge K$
\begin{eqnarray}
|x(k)| &\le& |x(k)-x_m(k)| + |x_m(k)-x_N(k)| + |x_N(k)| \\
&<& |x(k)-x_m(k)| + {2 \over 3}\epsilon
\end{eqnarray}
Now choose $m \ge N$ (which will, in general, depend on $k$) such that
$|x(k)-x_m(k)| < {1\over 3} \epsilon$, and we see that
$|x(k)| <\epsilon$. Hence $x (k) \to 0$ and so $x \in c_0$.
Showing that $x_n \to x$ is similar: Let $\epsilon>0$ and choose
$N$ such that if $m,n \ge N$ then
$d(x_n,x_m) < { 1\over 2} \epsilon$. Then, for $m,n \ge N$ we have
\begin{eqnarray}
|x(k)-x_n(k)| &\le& |x(k)-x_m(k)| + |x_m(k)-x_n(k)| \\
&<& |x(k)-x_m(k)| + {1 \over 2} \epsilon
\end{eqnarray}
Now choose $m \ge N$ (which will, in general, depend on $k$) such that
$|x(k)-x_m(k)| < {1 \over 2} \epsilon$, then we see that
$|x(k)-x_n(k)| < \epsilon$ for all $n \ge N$, and so $d(x,x_n) \le \epsilon$.
Best Answer
$\Bbb R$ is a complicated example. Let's instead consider a simple example. Let $S$ be the space $\{7, 8\}$ with the usual distance. (That is, $d(7,7) = d(8,8) = 0, $ and $d(7,8) = d(8,7) = 1$.) I claim that $S$ is a complete space.
We are not going to show this by considering every cauchy sequence one at a time. As you observed, that is impossible.
Let $C$ be a cauchy sequence and the elements of $C$ are $c_0, c_1, \ldots$. Since $C$ is a cauchy sequence, we have, for any positive $\epsilon$, that elements of the sequence that are far enough out will be closer than $\epsilon$. Formally, for any given positive $\epsilon$ there is some integer $N$ so that for any $i,j>N$, we have $d(c_i, c_j) < \epsilon$.
Take, for example, $\epsilon = \frac12$. Then because $C$ is cauchy, we know there must exist some $N$ such that for any $i,j>N$, we have $d(c_i , c_j) < \frac12$, because that is what it means for $C$ to be cauchy; that is the definition.
But if we have $d(c_i , c_j) < \frac12$ then $d(c_i , c_j) = 0$, because the only possible values of $d(\ldots)$ are $0$ and $1$, and it can't be $1$ because $1$ is not less than $\frac12$. So it must be $0$.
So we conclude that if $C$ is cauchy, then for all sufficiently large $i$, and $j$ we have $d(c_i, c_j) = 0$ and therefore $c_i = c_j$ for all sufficiently large $i$ and $j$. Thus, every cauchy sequence in $S$ is eventually constant. It might have a mixture of $7$s and $8$s at the beginning, but there must come some point (that's $N$) after which all the elements are $7$s or all the elements are $8$s. If this doesn't happen, then $C$ was not a cauchy sequence.
Since $C$ is eventually constant, there is some value, either $7$ or $8$, call it $L$, such that all sufficiently late elements of $c$ are equal to $L$. That is, there is some $N$ such that for any $i>N$, $c_i = L$, where $L$ is either 7, or 8, depending on which $C$ we actually chose.
Is is then trivial to show that $C$ converges to the value $L$. To show this we need to show that for any positive $\epsilon$, the terms of the sequence are eventually within $\epsilon$ of $L$. In this case we can do even better; we know that the terms of $C$ are eventually equal to $L$. $C$ is therefore a convergent sequence.
Therefore, all cauchy sequences in $S$ converge, and $S$ is therefore a complete metric space.
The same argument goes through just as well if we take the more complicated space $\Bbb Z=\{\ldots, -1, 0, 1, 2, 3\ldots\}$ with the usual distance function $d(i,j) = |i-j|$; the proof is exactly the same.
Mathematics is not (usually) about considering a lot of examples. It is about what properties logically imply which other properties. Just as we can prove that every square number is positive without considering each square individually, we can also prove that every cauchy sequence of elements of $\Bbb Z$ must converge, even without considering each cauchy sequence individually.