Clustering based on partial information?
You may need to treat this as an optimization problem.

Without a formal notion of what should be a cluster, you will not be getting far. A blackbox algorithm will not solve your problem, you need to open the box (understand the algorithm) and adjust it as necessary for your problem.

Once you have this notion, you can try to match it to algorithms. For example, if you can quantify similarity (e.g. if distance times attribute dissimilarity matches your desires) then you can try HAC. Or if you have thresholds (distance at most 100mi, attribute difference at most y) then you can run DBSCAN and merge neigh ors transitively into clusters.

But don't expect anything automatic.