TSP heuristics for limited distance information
There is no algorithm that runs in time $o(n^2)$ on an $n$-point metric space and returns a tour with weight within a constant factor of the minimum weight: see the argument in Section 9 of this paper by Indyk.

On the other hand, if you just want an approximation to the weight of the optimal tour, without actually getting a tour, then you can use this algorithm by Czumaj and Sohler. Their algorithm runs in time which is nearly linear in $n/\varepsilon^{O(1)}$ and returns a $1+\varepsilon$ approximation to the weight of minimum weight spanning tree. Since the minimum weight spanning tree is a factor 2 approximation to the minimum weight TSP tour, this gives a factor $2+\varepsilon$ approximation for TSP.

Of course these are worst-case bounds, but I find it implausible to be able to find a good tour by querying $o(n^2)$ edges unless you know more about your metric space. Metric spaces are very general objects and it's easy to hide information while still satisfying the triangle inequality.