This is probably an insanely hard question, but given an abstract metric space, is there some way to determine whether it's a manifold with a Riemannian, or more generally a Finslerian, metric? If that's too hard, one could start off by assuming that the underlying space is a manifold. The example that got me thinking about this was the induced metric on the 2-sphere embedded in $R^3$…the underlying space is obviously a smooth manifold, and the metric should be smooth(the geodesics would even be great circles, as they are for the standard metric on $S^2$,) but I don't see how you could prove the triangle inequality pointwise, as you'd have to to show that it's Finslerian, let alone Riemannian. This example is already incredibly simple, since it's a homogeneous space with a the metric induced by being a subspace of another homogeneous space.
[Math] Characterization of Riemannian metrics
dg.differential-geometrymg.metric-geometry
Related Solutions
To Deane Yang, concerning the smoothness of geodesics. These issues have been studied by Hartman and his coauthors more than 40 years ago. Together with Calabi he claimed to prove that in a $C^{\alpha}$ continuous metric all geodesics are uniformly $C^{1,\alpha}$. (I do not have mathscinet access now, but I think the paper was called "On the smoothness of isometries", or something like that). The paper is not quite correct, the computations prove that geodesics are only $C^{1,\alpha /2}$ (this was observed at some point by Reshetnyak). The optimal regularity appears in my paper with Asli Yaman "On Hoelder continuous Riemannian and Finsler metrics" (I apologize for citing my own work). The starting point of all these computations is a metric characterization of $C^{1,\alpha}$ curves in metric terms (in terms of the distance of the midpoint of a pair of points on the curve and the image of the corresponding midpoint of the interval of the definition). It is contained in the work of Hartman, but is probably much older.
To Sergei Ivanov: The questions of extendibility of geodesics have also been studied by Hartman. I again do not remember the correct reference, but can check it on Monday. I think he constructs example of even $C^{1,\alpha}$ Riemannian metrics, for any $\alpha <1$, that do not have extendible geodesics. (For $\alpha =1$, the metric has curvature bounded from both sides).
Now the main point. I am very sorry and have to apologize for my previous short posting. I slightly misunderstood your question. But I hope that my answer was still correct. Is the following more detailed explanation correct?
We assume that $t'>>t$ and want to prove that $d(\xi (t), \eta (t') )= d(\eta (t'), p) - cos (\alpha ) t + o(t)$. Here $o(t) /t \to 0$ and $\alpha$ is the "usual Euclidean " angle between $\xi$ and $\eta$.
The statement about the uniform "smoothness" of geodesics, show that it suffices to prove the claim in the case, when $\eta$ and $\xi$ are geodesics (since the "usual" angles between $\eta$ and any geodesic between $\eta (t')$ and $p$ goes to $0$).
Going on the geodesic $\eta$ first to the point $\eta (rt)$, with large, but fixed $r$, and then to $\xi (t)$, one obtains the right upper bound for $d (\eta (t'),p)$.
In a "general" metric space it would be now difficult to obtain the right lower bound of $d(\eta (t'),p)$. One could do it, if one knew that the geodesic $\eta$ was extendible beyond $p$. Then one could use a traingle inequality and the distance from $\xi (t)$ and $\eta (-rt)$. I hope I understood your question correctly and this was what you had in mind.
Here one can use another trick to obtain a lower bound. Observe namely, that from the "smoothness" of geodesics the "usual" angle between $\xi$ and any geodesic from $\eta (t') $ to $\xi (t)$ is very close to $\alpha$ (goes to $\alpha$ , with $t' \to 0$). Now we just look at the triangle $\xi (t),p, \eta (t')$ from $\xi (t)$ and not from $p$. The inequality obtained in point 3. above gives us the right upper bound of $d(\eta (t'),p)$.
Just a side remark. Your question is very closely related to the question about the correctness of the first formula of variation. I have thought about that question and proved that the formula holds true in Riemannian manifolds with Hoelder continuous metrics in "Differentiation in metric spaces". I just hope that the above proof is correct. Other wise the corresponding statement in my paper is wrong as well.
If you forget about the Riemannian metric, you should also forget about the tangent bundle and manifold structure. Then you end up with metric spaces of inner type or Aleksandrov spaces, where you can find a continuous curves with arc-length the distance. Look at "M. Gromov: Metric structures for Riemannian and Non-Riemannian Spaces, Birkhaeuser 1999".
Added in edit: Interesting remarks by Thomas Richard and Igor Belegradek. Answering a remark by the OP: You can define a "geodesic structure" by requiring an exponential mapping with some properties. If you differentiate this you end up with the geodesic spray, a certain vector field on $TM$. If you differentiate this again and flip coordinates, you get a vector field on $TTM$ whose integral curves project to Jacobi fields, velocity fields of geodesics, etc. See 22.6-22.9 of here, and also this paper. But this is not the route of low regularity.
Best Answer
If $X$ is a metric space and $x$, $y\in X$, a segment from $x$ to $y$ is a subset $S\subseteq X$ such that $x$, $y\in S$ and $S$ is isometric to $[0,d(x,y)]$.
Let now $n\in\{1,2,3\}$ and let $X$ be a metric space which is locally compact, $n$-dimensional and such that (i) every two points are the endpoints of a unique segment, (ii) if two segments have an endpoint and one other point in common, then one is contained in the other, and (iii) every segment can be extended, at either end, to a larger segment. Then $X$ is homeomorphic to $\mathbb R^n$.
This is a metric characterization of $\mathbb R^n$ for small $n$. Using it locally, you get a characterization of topological manifolds of small dimension. I imagine higher dimensions or smoothness are harder to come by...
The theorem above, along with quite a few other nice results, is proved in [Berg, Gordon O. Metric characterizations of Euclidean spaces. Pacific J. Math. 48 (1973), 11--28.]
LATER...
Of course, the paper [Nikolaev, I. G. A metric characterization of Riemannian spaces. Siberian Adv. Math. 9 (1999), no. 4, 1--58.] is relevant here! The paper gives purely metric characterizations of Riemannian manifolds of all smoothnesses up to $C^\infty$. The MR review gives a small history of the problem and references to earlier work.