MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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$.
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,\pi]$ [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(x) h^{-1}(x) = x+x^3$.) 1 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,\pi]$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(x) = x+x^3\$.)