A friend asked this question and I couldn't give a concrete answer. If we take out "extendable", then it's clear an open ball solves the problem. If we take out "non complete", then a cap of a sphere solves the problem. If we mantain both, however... I can't think of an example! The cone without its vertex is a non complete, non extendable manifold, but I think its geodesics don't satisfy the requirements.
I'd be grateful if anyone could shed some light on this! Maybe there are no such examples, but I really wanna know one way or the other.
One picture of the cone examples Kajelad and Moishe Kohan mention is a sector of a Euclidean disk; the blue arrows are joined when the cone is rolled up, and the two unshaded sectors are identified. Convexity of the quarter disk assures existence of a minimizing geodesic between arbitrary pairs of points.
Qualitatively, non-extendability of the cone metric arises from "collapsing in one direction." A different type of example, not immersable in Euclidean three-space, comes from "infinite expansion in one direction." Consider the open strip $(-1, 1) \times (-\infty, \infty)$ equipped with the metric $$ g = dx^{2} + \frac{dy^{2}}{1 - x^{2}}. $$ Existence of geodesics is qualitatively clear: The vertical component of the metric blows up at the boundary, so a length-minimizing path between two points at different heights is coaxed to travel toward and run (nearly) along the vertical axis, and does not leave the strip.
This metric is incomplete because horizontal segments are geodesics of length $2$, but does not extend because "distinct points on a boundary line are infinitely far apart."