The recent paper On the Erdos distinct distance problem in the plane
Authors: Larry Guth, Nets Hawk Katz prodded me to get a non-trivial example. Here is what I cannot find: an example of 12 distinct points in the plane with only 5 different distances between points. The regular 12-polygon has 6 different lengths but I cannot do better. http://oeis.org/A186704 implies that there is one>
Erdos Distance Problem – Case for n=12
co.combinatoricserdos
Related Solutions
Note that any metric with unique infinite geodesics on $\mathbb R^2$ has this property. In particular, hyperbolic plane as noted by Heather Macbeth. It also includes Minkowski plane with smooth ball and all complete negatively curved Riemannian metrics on $\mathbb R^2$.
So it is better to ask:
Is it true that the function $p$ is the only possible? ($p(a,b,c)=0,1,$ or $2$ when the triangle inequality for a,b,c, correspondingly, fails, turns into equality, or is strict.)
Is it true that space has to be homeomorphic to $\mathbb R^2$?
Sketch for locally compact case You condition implies existence of line (i.e. infinite minimizing geodesic) through any pair of points. Such line must be unique; otherwise for some values $p(a,b,a+b)=\infty$ for some values $a,b$.
If space is locally compact then line depends continuousely on the points. For some points $a_1, a_2, a_3, a_4$ take geodesic $a_1a_2$ connect each point to $a_3$ and connect each point of this trianle to $a_4$. This way we get a cone-map of 3-simplex in your space. If it is nondegenerate (i.e. the image does not coinsides with image of its boundary) then it would be easy to get a triple of small numbers $a,b,c$ such that $p(a,b,c)=\infty$ thus we arrive to a contradiction.
Thus the space must be 2-dimensional and with unique infinite geodesics --- I bet it should be homeomorphic to $\mathbb R^2$. Then it follows that $p(a,b,c)=0,1$ or $2$ as defined above.
There's a nice book by Garibaldi, Iosevich, and Senger, The Erdős Distance Problem, in the Student Mathematical Library series of the American Mathematical Society (AMS link). Mostly it's about the problem in the plane, but there is some discussion of, and references to, work on higher dimensions.
Best Answer
Here goes my poor explanation:
Take a regular hexagonal lattice with distance 1 between nearest neighbors, and choose a 15-point equilateral triangle in this lattice (15 is a triangular number). Remove the 3 vertices of the triangle. You'll be left with 12 points and 5 distinct distances.
Edit: Just checked the OEIS reference, and it's available on Google Books. The picture you want is on page 200.