Concerning the second question. A single closed geodesic is not enough. For example, let $S$ be the equator of the standard sphere. All distances between points of $S$ are realized by paths in $S$, so you don't have any information about the metric outside $S$, except that it is sufficiently large (so that the paths outside $S$ are not shorter).

On the positive side, for every 2D Riemannian manifold, you can construct an embedded graph $S\subset M$ such that the distances between its points determine the metric uniquely (up to an isometry). It suffices to take a union of small geodesic circles such that their encircled regions cover $M$ and lie within convexity radii of their centers. Indeed, a metric on a 2-disc whose boundary is convex and whose geodesics are all strictly minimal, is uniquely determined by the distances between boundary points.

This used to be a long-standing conjecture and was proved in 2005 by Pestov and Uhlmann:
"Two dimensional compact simple Riemannian manifolds are boundary distance rigid", Ann. of Math. 161 (2005), no. 2, 1093--1110; MR2153407 (2006c:53038).

In higher dimensions, the full conjecture is still open. Until very recently, it was known only for very special metrics (some locally symmetric ones and some splitting ones). Dima Burago and I proved it for sufficiently small regions in any Riemannian manifold, where "sufficiently small" actually means that the diameter is small relative to the maximum modulus of sectional curvature (and of course to the injectivity radius). This is in our paper "Boundary rigidity and filling volume minimality of metrics close to a flat one", Ann. of Math. 171 (2010), no. 2, 1183--1211.

So, as Will Jagy suggested in his answer, you can take the $(n-1)$-skeleton of a sufficiently fine triangulation for $S$.

I am not aware of any numerical algorithms for this problem. It is known that the solution is stable (depends continuously on the input data) but you have to take into account the derivatives of the boundary distance function. A $C^0$ approximation of the distances is not enough to find an approximation of the metric, see Paul Siegel's answer.