Distance matrix based classification algorithms

Graph-based and kernel-based algorithms can surely be an option as Alexandre suggests. However, using random projections, you can also actually extract explicit features given a kernel matrix. See this Balcan & Blum Kernels as Features paper that describes this idea. Once you get the features, you can just train any standard classifier using them. This is in fact also somewhat similar in spirit to the idea of using MDS on pairwise distances to compute a low dimensional representation, as Shuo suggests.

You should be able to use MDS to place your documents into some subspace. Once they are in this subspace, any classification algorithm should be able to do the rest.

Alternatively, you may be able to use spectral clustering to place your documents into a latent space. This approach is more semi-supervised, but should yield fairly accurate predictions.

You can use any graph-based algorithm (similar to the semi-supervised learning setting), any kernel-based algorithm (libsvm for example allows you to define your own kernel, and something like K(x,y) = max_dist - dist(x,y), or exp(-dist(x,y)) should do as a kernel), and this includes gaussian processes. To classify a new example in the kernel-based setting all you need is its distance to the support vectors.