I don't have an answer for your whole class of graphs, but three subclasses of graphs that have this property are the distance-hereditary graphs, chordal graphs, and median graphs.
Distance-hereditary graphs are defined by the property that every connected induced subgraph has the same distances. So you can pick an arbitrary starting vertex $v_1$ and then choose each successive vertex to be any not-already-chosen vertex that is adjacent to a previously-chosen vertex.
The chordal graphs are the graphs that have an ordering with the property that each successive vertex, when added, has a clique for its neighbors. This ordering is obviously distance-preserving.
Similarly, median graphs (including your grid example) have the property that, for any breadth-first ordering, each vertex has a hypercube neighborhood at the time it is added. (See pages 76–77 of Eppstein et al, "Media Theory", Springer, 2008). Again, this property means that the addition cannot change the distances among the previous vertices.
There's a class of graphs that I don't know a name for, generalizing both chordal and distance-hereditary graphs, that can be recognized in polynomial time and that have your property. They are the connected graphs that can be built up from a single vertex by adding vertices one by one, where the neighbors of each new vertex are a subset of one of the closed neighborhoods of the previous graph. They are almost (but not quite) the same as the dismantlable graphs, the difference being that the new vertex does not have to be adjacent to the vertex whose neighborhood is being copied. An elimination ordering of a chordal graph is a construction of this type where each new vertex chooses a clique subset of a neighborhood. Similarly distance-hereditary graphs have a construction of this type where the neighbors of each new vertex are an entire closed neighborhood, an open neighborhood, or a single vertex. Each new vertex can't change the distances of the previous vertices, so this construction sequence has the property you're looking for.
If you define a vertex v to be "removable" if it could be the last one in this sequence (it has an open neighborhood that is a subset of someone else's closed neighborhood) then removing other removable vertices doesn't change the removability of v: if v's neighborhood is a subset of u's, and we remove u as having a neighborhood that is a subset of w's, then v is still removable because its neighborhood is still a subset of w's. Therefore, the sequences of removal steps that we can follow to take a graph back down to nothing form an antimatroid, and one such sequence can be found in polynomial time by a greedy algorithm that repeatedly removes a removable vertex whenever it can find one. Reversing the output of this algorithm gives the construction sequence for the given graph. The graph of the cube gives an example of a graph that has your property (a median graph) but is not constructible in this way. I think the median graphs that can be constructed in this way are exactly the squaregraphs (which include the regular grids). The graphs that have a construction sequence of this type also include all graphs that have a universal vertex, such as the wheel graphs, so (unlike chordal graphs and distance-hereditary graphs) they are not perfect and not closed under induced subgraphs.