Is it possible to prove that all Cauchy sequences of real numbers converge without using the Bolzano-Weierstrass theorem?
Let $(x_n)$ be convergent, with limit $x$. It is also a Cauchy sequence by the estimate $|x_p-x_q|\leq|x_p-x|+|x_q-x|$.
For the other direction, suppose $(x_n)$ is Cauchy. Since it's bounded, we can define $x\in\mathbb{R}$ to be the limit superior of the $x_n$. Let's check that the $x_n$ converge to $x$:
Fix $\varepsilon>0$. Let $N\in\mathbb{N}$ be such that $|x_p-x_q|<\varepsilon/2$ for all $p,q>N$. Let $n>N$ be such that $|x_n-x|<\varepsilon/2$. Then, for all $k>n$, we have $|x_k-x|\leq |x_k-x_n|+|x_n-x|<\varepsilon/2+\varepsilon/2=\varepsilon$. Convergence follows.
You can prove it by nesting intervals.
Suppose $(x_n)$ is a Cauchy sequence. Then it is bounded (easy lemma), say it is contained in $[a_0,b_0]$ and set $d=b_0-a_0$.
Since the sequence is Cauchy, there exists $k_1$ so that, for $m,n>k_1$, $|x_m-x_n|<d/4$; in particular, there exists a subinterval $[a_1,b_1]\subseteq[a_0,b_0]$ with $b_1-a_1=d/2$ so that $x_m\in[a_1,b_1]$ for all $m>k_1$.
We can now start a recursive procedure: if we have found a subinterval $[a_r,b_r]$ with $b_r-a_r=d/2^r$ and $k_r$ so that $x_m\in[a_r,b_r]$ for $m>k_r$, then we can find, with the same method as above, $[a_{r+1},b_{r+1}]\subseteq[a_r,b_r]$ and $k_{r+1}$ so that $b_{r+1}-a_{r+1}=d/2^{r+1}$ and, for $m>k_{r+1}$, $x_m\in[a_{r+1},b_{r+1}]$.
Note that the sequence $(a_r)$ is increasing and the sequence $(b_r)$ is decreasing; they converge to the same limit $l$, as $\lim_{n\to\infty}(b_r-a_r)=\lim_{r\to\infty}d/2^r=0$.
Prove that $\lim_{n\to\infty}x_n=l$.
Spivak's Calculus contains a low-tech proof that every real sequence contains a monotone subsequence:
Definition: If $(x_{n})$ is a real sequence, define a peak point to be an index $N$ such that $x_{m} \leq x_{N}$ for all $m > N$.
In words, if $N$ is a peak point of $(x_{n})$, then no subsequent value exceeds $x_{N}$.
Theorem: If $(x_{n})$ is a real sequence, there exists a monotone subsequence $(x_{n_{k}})$.
Proof (sketch): If $(x_{n})$ has infinitely many peak points, it's easy to construct an increasing sequence $(n_{k})$ of peak points. The corresponding subsequence is non-increasing by the definition of a peak point.
If $(x_{n})$ has only finitely many peak points, let $n_{1}$ be an index larger than every peak point. Since $n_{1}$ is not a peak point, there exists an index $n_{2} > n_{1}$ such that $x_{n_{2}} > x_{n_{1}}$. Continue inductively, constructing a strictly increasing subsequence.
The Bolzano-Weierstrass theorem follows easily, since it's readily proved that a bounded, monotone sequence of reals is convergent.