Obviously, k-means needs to be able to compute means.
However, there is a well-known variation of it known as k-medoids or PAMk-medoids or PAM (Partitioning Around Medoids), where the medoid is the existing object most central to the cluster. K-medoids only needs the pairwise distances.