Some clustering algorithms can use spatial index structures. This allows for example DBSCAN and OPTICS to run in $O(n\log n)$ time (as long as the index allows $O(\log n)$ queries).
Obviously, an algorithm that runs in this complexity does not build a $O(n^2)$ distance matrix.
For some algorithms, such as hierarchical clustering with single-linkage and complete-linkage, there are optimized algorithms available (SLINK, CLINK). It's just that most people use whatever they can get and whatever is easy to implement. And hierarchical clustering is easy to implement naively, using $n$ iterations over a $n^2$ distance matrix (resulting in an $O(n^3)$ algorithm ...).
I'm not aware of a complete list comparing clustering algorithms. There probably are 100+ clustering algorithms, after all. There are at least a dozen k-means variants, for example.
Plus, there is run-time complexity as well as memory complexity; there is average-case and worst-case. There are huge implementation differences (e.g. single-link mentioned above; and DBSCAN implementations that do not use an index, and thus are in $O(n^2)$, and while they do not need to store the full $n\times n$ distance matrix, they then still need to compute all pairwise distances). Plus there are tons of parameters. For k-means, $k$ is critical. For pretty much any algorithm, the distance function make a huge difference (any many implementations only allow Euclidean distance ...).
And once you get to expensive distance functions (beyond trivial stuff like Euclidean), the number of distance computations may quickly be the main part. So you'd then need to differentiate between the number of operations in total, and the number of distance computations needed. So an algorithm that is in $O(n^2)$ operations but only $O(n)$ distance computations may easily outperform an algorithm that is $O(n \log n)$ in both, when the distance functions are really expensive (say, the distance function itself is $O(n)$).