DC proves the statement.
The first lemma is an easy consequence of the triangle inequality (and doesn't use DC):
Lemma 1: If $r$ is between $p,q$ and $s$ is between $p,r$, then $s$ is between $p,q$. (So we have the picture $p$ .... $s$ .... $r$ .... $q$).
Lemma 2: Let $p,q$ be distinct points and $\varepsilon>0$. Then there is $r$ which is between $p,q$ and with $d(p,r)<\varepsilon$.
Proof: Suppose $p,q,\varepsilon$ constitute a counterexample. For $r$ which is between $p,q$, or for $r=q$, let $$\sigma(r)=\inf\big\{d(p,s)\bigm|s\text{ is between }p,r\big\}.$$ Note that $\sigma(r)\geq\varepsilon$. (We have $\sigma(q)\geq\varepsilon$ by choice of $p,q,\varepsilon$. If $r$ is between $p,q$ and $\sigma(r)<\varepsilon$ then letting $s$ be between $p,r$ with $d(p,s)<\varepsilon$, then by Lemma 1, $s$ is between $p,q$, contradicting the choice of $p,q,\varepsilon$.)
By DC, we can find a sequence $\left<r_i\right>_{i<\omega}$ such that $r_0=q$, and for each $i$, $r_{i+1}$ is between $r_i,p$ and $d(p,r_{i+1})<\sigma(r_i)+\frac{1}{2^i}$. Note that $\left<r_i\right>_{i<\omega}$ converges to some $r$, and $r$ is between each $r_i$ and $p$. Now let $s$ be between $r$ and $p$. Let $i$ be such that $d(s,r)>\frac{1}{2^i}$. Then note that the existence of $s$ contradicts the choice of $r_{i+1}$.
The proof of the existence of midpoints is similar to that of the lemma.
Suppose that $p,q$ are distinct but there is no midpoint between $p,q$.
Given $r$ with either $r=p$ or $r$ is between $p,q$ and $d(p,r)<d(r,q)$, let $$\tau(r)=\sup\big\{d(p,s)\bigm|s\text{ is between }r,q\text{ and }d(p,s)<d(s,q)\big\}.$$ Note that by Lemma 2, the supremum here is taken over a non-empty set. Using DC, construct a sequence $\left<r_i\right>_{i<\omega}$ such that $r_0=p$, $r_{i+1}$ is between $r_i$ and $q$, and $d(p,r_{i+1})>\tau(r_i)-\frac{1}{2^i}$. Note that $\left<r_i\right>_{i<\omega}$ converges to a limit $r$, and $r$ is between $r_i$ and $q$ for each $i$. Note that $d(p,r)\leq d(r,q)$, and since there is no midpoint between $p,q$, therefore $d(p,r)<d(r,q)$. So $\tau(r)$ is defined and $d(p,r)<\tau(r)$. Let $i$ be such that $d(p,r)+\frac{1}{2^i}<\tau(r)$. Then there is a point $s$ which is between $r,q$ and $d(p,s)>d(p,r)+\frac{1}{2^i}$. But then the existence of $s$ contradicts the choice of $r_{i+1}$.