Clearly, completeness gives us the existence of at least one geodesic $\gamma:[0,1]\to M$ such that $\gamma(0)=p$ and $\gamma(1)=q$, however, this geodesic need not be length minimizing. I strongly suspect length minimizing geodesics must exist, but I can't quite construct the argument for their existence in full detail. This is what I've come up with.
If we let $r=d(p,q)$, and $U= B(p,2r)\cup B(q,2r)$, then by completeness, $U$ is a precompact open in $M$. If we define $\Gamma$ to be the set of smooth (or sufficiently regular) paths $\gamma:[0,1]\to M$ with b.c. $\gamma(0)=p$ and $\gamma(1)=q$, and define $\Gamma_0\subset \Gamma$ to contain those paths $\gamma $ with image in $\overline U$, then we may apply the direct method of calculus of variations to minimize the energy functional $$ E:\Gamma\to\mathbb R,\quad E[\gamma]=\int_0^1\! |\dot\gamma(t)|\,\mathrm dt. $$ To do so, we define a weak topology on $\Gamma$ under which $\Gamma_0$ is weakly compact and $E$ is lower-semicontinuous, so that we may obtain a geodesic of minimal length.
The tricky thing here, of course, is to find a suitable weak topology, on a suitable candidate space $\Gamma$, such as $H^1(0,1;M)$ with boundary conditions. Naïvely, I would $H^1(0,1;M)$ to suffice, with a weak topology defined via coordinate charts, but before going through the calculations, I'm wondering if there's already a reference for this result, with a clean proof.
Jurgen Jost also gives a proof in Riemannian Geometry and Geometric Analysis, chapter 1.5. It's only for compact manifolds (complete manifolds are in chapter 1.7), but you already figured out how to deal with this problem.
In short, it's enough to take $\Gamma$ as the class of Lipschitz curves $\gamma \colon [0,1] \to U$ with constant speed. One can easily modify such curves to be piecewise geodesic, and then the compactness argument is very elementary, since every curve is represented just by a finite collection of points.