Is it necessary for a distance measure used in clustering to correspond to some valid vector space? I have defined an distance measure based on some properties of points. But I'm not even sure that it corresponds to a valid distance in some vector space. Is this a necessary condition for clustering ? If yes, how do I check that it's a valid distance in some vector space. Just like Mercer's theorem can verify that the kernel is an valid cross product in some valid vector space, are there any such tests for distance ? 
 A: Look closely at the actual algorithms. There is no general rule.
Some will require metric properties, other just assume you have some dissimilarity, and can trivially be rewritten to use similarity measures instead.
For example DBSCAN (see "Generalized DBSCAN") doesn't actually use the distances, but is only interested in a binary threshold decision to discern "near" and "far" objects. Metric properties allow the algorithm to run faster, by performing this selection efficiently.
k-means on the other hand is actually not even using distance, but as it tries to minimize variance, it assigns each objec to the mean with the smalles "sum of squared deviation". And the sum of squared deviations is the squared Euclidean distances. As taking the root of this value, this means each object is assigned to the closest mean by Euclidean distance. It is not mathematically correct to use other distances with k-means (although it may work, at least if the mean function minimizes the distances; otherwise k-means may no longer converge!) - the reason why in k-means we assign points to the nearest mean is not to minimize distances, it is to minimize the total sum of variances. This ensures convergence: reassignment reduces variances, and recomputing the means also reduces variances. As there are only a finite number of assignments, we must at some point stop.
On a side note, try to approach clustering from the "knowledge discovery" point of view, not from "learning". You want to discover something new with clustering, not reproduce something you already know; so it is pretty much the exact opposite of learning labels.
