All you need to do is to go beyond k-means and hierarchical clustering to somewhat more modern methods (if you consider 1990s to be "modern", that is).
Many clustering methods such as DBSCAN do not require your distance to be metric. The whole notion of a metric is of low relevance for data mining, as databases may contain duplicate records, so at best you have a pseudo-metric anyway.
Many just need some kind of similarity measure. It could even measure similarity instead of distance, that is just a different sign for the threshold to them.
DBSCAN needs a threshold. OPTICS when using the $\xi$ method for extracting clusters also needs them to bear some semantics, i.e. a drop in distance of 10% being interesting enough to start a new nested hierarchical cluster.
If you have a metric (or pseudo-metric), that can bear performance benefits. If you already have a distance matrix, these are moot, because that already means you computed the $O(n^2)$ similarities.
K-means, while very popular, has much stronger restrictions. In particular, the mean must minimize the distances, i.e. updating a cluster center with the mean of the objects must improve the criterion function. This will likely not hold for you, if you can compute distances from mean vectors at all.
You might want to have a look at "Generalized DBSCAN" to understand how loose the dependency on the distance function is. It's just a method for selecting "neighbor" objects. But you can in fact plug in any other definition of "neighbor".