This is not even true on the circle. In that case, given any metric that comes from a Riemannian metric there is a constant $c>0$ such that there is a diffeomorphism of the circle with itself that carries the metric to $c$ times the standard metric:
$$
d\bigl((x_1,y_1),(x_2,y_2)\bigr) = \cos^{-1}(x_1x_2+y_1y_2).
$$
If you now take $d' = h\circ d$ where $h$ is any continuous, strictly increasing subadditive function on $[0,\infty)$ that satisfies $h(0)=0$, then you'll get a new metric $d'$. If $h$ is smooth and satisfies $h(x)^2 = x^2g(x^2)$ where $g$ is a smooth function with $g(0)\not=0$, then the square of $d'$ will be smooth (and nondegenerate) near the diagonal in $S^1\times S^1$, but, in general, $d'$ will not come from a Riemannian metric, for the same reasons that Vladimir gave in his answer. (The main advantage of this counterexample is that it produces examples that do not come from a Riemannian metric in any neighborhood of the diagonal, unlike Vladimir's example. For example, just take $h^{-1}(x) = x+x^3$.)

**A second source of examples:** Another way to construct examples is to embed $M$ into another Riemannian manifold so that the image is not totally geodesic (for example, any smooth embedding into $\mathbb{E}^m$ will do since you assumed that $M$ is compact). Then the restriction of the ambient Riemannian distance function to $M\times M$ will have the properties that you want, but it won't make $M$ into a length space (since the shortest curves joining to points in $M$ that lies entirely in $M$ won't be a geodesic in the ambient space), so such a distance doesn't come from Riemannian metrics on $M$.