Just an initial association—one kind of preprocessing based only on distances is metric indexing. There are even some specific, simple structures for integer metrics, like in your case. That'll only let you retrieve all nodes within a given distance, but maybe you could use the basic ideas somehow?
For example, one common idea in metric indexing is is to use sample objects as pivot points in the distance space, and to use the triangle inequality to find cheap heuristics and bounds for the (expensive) actual distance. Applied to your example of a graph $G=(V,E)$ with $n$ nodes under the unit-weight graph geodesic $d(\cdot,\cdot)$, you could select a subset $P\subset V$ of $m$ pivot nodes, and then pre-compute an $n\times m$ matrix $T$ of distances.
Assuming one-to-one shortest path (given your mention of $A^*$), if you're going from $s$ to $t$, you would then fetch two rows $x=T[s]$ and $y=T[t]$, and compute $h(s,t)=L_\infty(x,y)$, which is simply $\max_{i=1\ldots m} |x_i-y_i|$. Because of the triangle inequality, this will be a lower bound to the the actual distance $d(s, t)$, i.e., $h(s,t)\leq d(s,t)$. (See my tutorial for a more thorough explanation.) The heuristic is (as mentioned) guaranteed to be a lower bound, and the more pivots you add, the tighter it will (probably) be. Randomly selected pivots work well in practice, so the method is really simple.
In metric indexing, this lower-bounding heuristic is used for filtering out candidate objects during search (we only want close objects, so those guaranteed to be far away are eliminated). In your case, you could use the bound as a heuristic for $A^*$. Because it's a lower bound, $A^*$ will work correctly, and the number of pivots is a parameter for you to set. The more memory you have, the better your heuristic will be. It works for any starting node and any ending node, and it's really simple. And, as requested, for a constant number of pivots, it takes $\mathcal{O}(n)$ memory.
As for the number of pivots needed—there is some contention in general. Some people claim the optimal number grows with data size (e.g., logarithmically), and some claim it's a function of the inherent hardness of the distance function, regardless of problem size. I guess you could experiment. And while there are specialized algorithms for picking out good pivots, you could just try random ones first; they usually work quite well.
(Come to think of it, I once read some papers on using waypoint or somesuch with $A^*$. I don't remember the details, but that, too, was based on selecting some representative nodes and using them—probably in a manner at least similar to what I've described. I have a look and see if I can find that material again.)
