Clustering based on partial information? I'm open to suggestions on how to improve the title.

My problem is this, but I think it's a more general problem. In my context, I have a lot of data which has location data (Lat/Lon) as well as various characteristics of my objects.  I'm interested in clustering based on location in such a way that it controls for effects based on weather and other local effects.

So what I want is a clustering which, after trained, determines the cluster of a new object solely based on its GPS coordinates. However, I want the clusters not to just cluster based on locational clusters (there are lots of objects in this ball in Florida, this ball in California, etc.) but to make clusters so that within the clusters, objects are more similar than you would expect.

So for example, k-means would not accomplish this; it would just identify pockets of objects based on location clustering, or it would require more information to determine the cluster of a new object (neither are desirable).

Another way would be to run k-means a bunch of times, rate the results based on comparing homogeneity within clusters, and pick the best, but this seems both computationally annoying and unlikely to get good results (it would tend to identify circular clusters, rather than e.g. picking out things within 10 miles of a coast, or whatever turns out to be useful).

I feel like someone has thought of this before and come up with something.  What sorts of algorithms (classical or not) might help with this?

I don't mind re-implementing something on my own, and I don't mind stacking/etc. classifiers.  My dataset is fairly small for now, so even if there isn't a fast algorithm for this, it should be okay (even $O(n^2 \log(n))$ algorithms are doable, I've found).
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.