I suspect you've missed my point, probably because of an insufficient background in special relativity, which one really needs to learn (and learn well) before one tries to tackle general relativity.
The reason I suspect you've missed the point is you are still worried about coordinate systems in spite of my previous remarks.
Distances don't depend directly on the choice of coordinates, except insofar as the coordinates impose some sort of notion of simultaneity.
For instance, one can calculate distances in polar coordinates, or we can calculate them in cartesian coordinates. Or any other sort of coordinates, really.
I hope this is obvious, though I'm getting the niggling feeling that you might NOT know the details of how to compute distances in polar coordinates, and thus out of a sense of caution based on ignorance think that the coordinates do matter.
Coordinates are just a choice of labels - they don't really matter to anything physical.
I'll get back to simltaneity later. For now, I'll assume that you use the more-or-less usual notion of simutlaneity, that of static observers use, in which case you will find that your spatial slices (the slices of space-time of constant time are curved). This isn't any more - or less - scary and complicated than measuring distances on the curved surface of the Earth.
You might have seen the pictures of how the spatial slices are curved, they look like this:
http://en.wikipedia.org/wiki/File:Flamm.jpg
http://en.wikipedia.org/wiki/File:Flamm.jpg
[I'm not sure why the image isn't displaying? I'll put in the link...]
Note that there is no coordinate system for the surface of the Earth in which you measure distances by just subtracting coordinates. If that's your ultimate goal, it's doomed to fail in GR on the above surface (called a Flamm's paraboloid), just as it is doomed to fail on the surface of the Earth. To deal with measuring distances you'll need to learn techniques that are more complicated mathematically than just subtracting coordinates.
Going back to the notion of simultaneity:
The notion of simultaneity is important to defining distances. Length contraction in SR is the cannonical example.
See any of the mega threads about length contraction, and/or the simultaneity of light flashes, to get more details on how length contraction and the relativity of simultaneity intertwine.
Fundamentally, the Lorentz interval is what different observers agree on. They specifically do not agree on "distances" or times, in general. They DO agree on the Lorentz interval.
In GR specifying the notion of simultaneity is trickier than it is in SR. Definining a coordinate system, which defines surfaces of constant time by a constant "t" coordinate, is one way of defining the notion of simultaneity, but perhaps not the only one. But fundamentally it's not the coordinate choice that matters, what matters is the notion of "now", the notion of "simultaneity".
To wrap it up - distance is just the length of some curve. The devil is in the details - what curve, exactly?