I have a new data point and want to classify it into the existing classes.I can calculate pairwise distance for the new point to all existing points(in the existing classes). I know using KNN would be a straightforward to classify this point. Is there a way I could randomly sampling existing classes and then correlated the new point to a potential classes without calculating all pairwise distances?
I think you need to take a step back and figure out what you're trying to do at a higher level.
How were the existing classes built? If they were built by clustering unlabeled data, then with this new data point you're continuing with the clustering process.
If the existing classes are labeled data, then k-NN is one possible classification method, and there are plenty more (decision trees, naive bayes, neural networks, etc.).
If you're doing clustering, then there are several ways of assigning a point to a cluster, among measuring the distances from the point to cluster centroids is one. There's also single-linkage (distance is min of distances from point to points of cluster), complete-linkage (max of distances). These different methods will give clusters with different shapes and there's no universally best approach. You could test them with points that are already in clusters... but then if you're certain of what classes they re in, then you have a classification problem.
So... if it's classification, then you can use k-NN, that's similar to the idea of assigning a point to a cluster according to distance. But it's not defined as finding the nearest cluster, it's defined as finding the classes of the k nearest points, then applying a vote or something. 1-NN is basically like single-linkage clustering. kNN does require finding the most similar (training) data points to your new data point. Sampling is definitely sub-optimal, but it may be good enough if you classes are well separated. If the cost of calculating distances is high, then one way of reducing the cost of calculation is the idea of skyline clustering: use a cheap distance metric to determine a subset of points that are likely to be among the k nearest neighbours, then compute these neighbours using the more expensive distance metric.
Finally, if you will be classifying many points and not updating your model, it may be worth training a model (e.g. a decision tree) on the existing classes.