Are there algorithms for clustering objects with pairwise distances, without computing all pairwise distances?
Well, one may argue that DBSCAN is based on all pairwise distances, but it uses data indexing to avoid computing all of them using geometric bounds.

And there are other examples if you browse through literature.

For example, the classic CLARA method is an approximation to PAM that avoids computing all pairwise distances.

And there are many more such techniques.