How to define a posterior probability of y given x when the model is not probabilistic? Suppose we have a very simple online k-means where each new data-point is assigned to its nearest center (the mean is updated incrementally). Each center (cluster) is labelled with the most common label of data-points assigned to that cluster. In this special configuration: is it possible to compute a sort of "posterior probability"? I.e., can the posterior probability of a class label $y$ given a data-point $x$ ($P(y|x)$) just be $1/\text{distance}(x, m_y)$, where $m_y$ is a center labelled with $y$ which is nearest to $x$?
 A: Since you can view k-means as a sort of impoverished Mixture of Normals (specifically with 0 variance), I'd be tempted to use the density function of the Normal distribution if you need a probabilistic metric. If you're willing to assume equal variances in all the clusters you can ignore the variance in the density function, and normalise by the distance across all clusters (you could also include a prior probability of the cluster as the fraction of points assigned to it as well).
It's not pretty and it's not really theoretically justified, but it may suffice.
A: As noted in the comments, k-means does correspond to a probabilistic model, just like PCA. The connection between machine learning and statistics (Naive-Bayes v. logistic regression) is one of my favorite topics, but that's neither here nor there...  As suggested, you could employ a full-blown mixture model to quantify that posterior probability of a new observation given observed data. This would give you some nice tools like posterior predictive checks to understand your model and data more completely. I recommend reading Andrew Gelman for more on that approach.
If you are wedded to k-means for practical reasons (i.e. you already implemented it or your boss knows k-means is the way to go), then you could still use some cool tricks to get a non-parametric posterior density estimate of new observations give your data (and estimated cluster centers). Namely, you could use k-nearest neighbors. In this case, you would be training nearest neighbor algorithm with class labels assigned by k-means. Thus, the posterior probability of a new datum belonging to class $i$ is the proportion of k-neighbors belonging to class $i$, i.e. $Pr(X_{new}=i|X_{obs})=\frac{k_i}{k}$. 
The reason this works is that nearest neighbor is a form of kernel density estimation. Unfortunately, the nearest neighbor classifier isn't a true kernel because it doesn't integrate to 1 as a true kernel (or probability distribution) should, but it's awfully close. This is awesome because a k-nearest neighbor classifier can be implemented to be quite fast with clever data structures, depending on the kind of data you have.
This lecture describes the ins and outs of the approach I have outlined above for a mixture of Gaussians, which is essentially what k-means is trying to get at.
