Clustering algorithm which does not require to tell the number of clusters
I would try DBSCAN algorithm first: fairly easy to tune (with, in particular, a notion of distance as you requested), and does not need to know the number of clusters.

There are a few other algorithms that can help you decide the number of clusters: Bayesian Gaussian Mixtures (see sklearn implementation) for instance, but it requires a bit more knowledge and work. There is also spectral clustering, but for this one, sklearn does not automatically find the number of clusters, so you will have to do create your own implementation and determine the number yourself, manually, by plotting the eigenvalues.