Which non-training classification methods are available?
What you are asking about is Instance-Based Learning. k-Nearest Neighbors (kNN) appears to be the most popular of these methods and is applicable to a wide variety of problem domains. Another general type of instance-based learning is Analogical Modeling, which uses instances as exemplars for comparison with new data.

You referred to kNN as an application that uses training but that is not correct (the Wikipedia entry you linked is somewhat misleading in that regard). Yes, there are "training examples" (labeled instances) but the classifier doesn't learn/train from these data. Rather, they are only used whenever you actually want to classify a new instance, which is why it is considered a "lazy" learner.

Note that the Nearest Template Prediction method you mention effectively is a form of kNN with k=1 and cosine distance as the distance measure.