Clustering based on similarity scores
I think a number of clustering algorithms that normally use a metric, do not actually rely on the metric properties (other than commutativity, but I think you'd have that here).  For example, DBSCAN uses epsilon-neighborhoods around a point; there is nothing in there that specifically says the triangle inequality matters.  So you can probably use DBSCAN, although you may have to do some kind of nonstandard spatial index to do efficient lookups in your case.  Your version of epsilon-neighborhood will likely be sim > 1/epsilon rather than the other way around.  Same story with k-means and related algorithms.
Can you construct a metric from your similarity?  One possibility: dist(ei, ej) = min( sim(ei, ek) + sim(ek, ej) ) for all k ...  Alternately, can you provide an upper  bound such that sim(ei, ej) &lt; sim(ei, ek) + sim(ek, ej) + d, for all k and some positive constant d?  Intuitively, large sim values means closer together: is 1/sim metric-like?  What about 1/(sim + constant)?  What about min( 1/sim(ei, ek) + 1/sim(ek, ej) ) for all k? (that last is guaranteed to be a metric, btw)
An alternate construction of a metric is to do an embedding.  As a first step, you can try to map your points ei -> xi, such that xi minimize sum( abs( sim(ei, ej) - f( dist(xi, xj) ) ), for some suitable function f and metric dist.  The function f converts distance in the embedding to a similarity-like value; you'd have to experiment a bit, but 1/dist or exp^-dist are good starting points.  You'd also have to experiment on the best dimension for xi.  From there, you can use conventional clustering on xi.  The idea here is that you can almost (in a best fit sense) convert your distances in the embedding to similarity values, so they would cluster correctly.
On the use of predefined parameters, all algorithms have some tuning.  DBSCAN can find the number of clusters, but you still need to give it some parameters.  In general, tuning requires multiple runs of the algorithm with different values for the tunable parameters, together with some function that evaluates goodness-of-clustering (either calculated separately, provided by the clustering algorithm itself, or just eyeballed :)  If the character of your data doesn't change, you can tune once and then use those fixed parameters; if it changes then you have to tune for each run.  You can find that out by tuning for each run and then comparing how well the parameters from one run work on another, compared to the parameters specifically tuned for that.