DBSCAN (see also: Generalized DBSCAN) does not require a distance.
All it needs is a binary decision. Commonly, one would use "distance < epsilon" but nothing says you cannot use "similarity > epsilon" instead. Triangle inequality etc. are not required.
Affinity propagation, as the name says, uses similarities.
Hierarchical clustering, except for maybe Ward linkage, does not make any assumption. In many implementations you can just use negative distances when you have similarities, and it will work just fine. Because all that is needed is min, max, and <.
Kernel k-means could work IF your similarity is a good kernel function. Think of it as computing k-means in a different vector space, where Euclidean distance corresponds to your similarity function. But then you need to know k.
PAM (K-medoids) should work. Assign each object to the most similary medoid, then choose the object with the highest average similarity as new medoid... no triangle inequality needed.
... and probably many many more. There are literally hundreds of clustering algorithms. Most should work IMHO. Very few seem to actually require metric properties. K-means has probably the strongest requirements: it minimizes variance (not distance, or similarity), and you must be able to compute means.
1-sim(ei, ej) = Distance. With distance metric you may apply for example hierarchical clustering. Going down from the root you will see at what level of granularity clusters would make sense for your particular problem. $\endgroup$