Okay, I came up with a few ideas:
Idea 1: Assume the training points are arranged in a regular grid or that if they are irregularly-spaced, we can make some transformation to a grid by choosing the closest point's classification for grid-points or something. Train independent classifiers on every grid point. Advantages: Highly parallelizeable. Disadvantages: Doesn't take advantage of spatial correlations because no learner is aware of the others. You have to keep a lot of classifiers around to build your model. And you lose a little information in the transformation to a grid if points are not already regularly-spaced. Points must be regularly spaced for this, because each classifier has to correspond to a particular (x,y) location in the grid for training to work.
Idea 2: Join (x,y) with X data to generate a larger training matrix, and train one classifier on this. Advantages: The classifier can learn spatial relationships and correlations very naturally. The final model only has one agent. Disadvantages: Not so naturally parallelizeable. Each row of X, corresponding to many (x,y) points, will be duplicated over and over in the join. Training is slow, meaning we would need some kind of data reduction on the grid points to make the join less explosively large.
Idea 3: The Label Powerset transformation, where one "create[s] one binary classifier for every label combination attested in the training set" and then at query-time selects the answer to be the label combination belonging to the binary classifier with highest confidence. Advantages: None in this context that I can think of. Disadvantages: The number of possible combinations in the output space is huge, so we almost certainly don't have enough data to train each binary classifier, and the number of these classifiers in the final model would be huge. And what about cases where the answer should really be something not seen in the training data? This can't handle that.
Idea 4: True multi-label classification to find all y labels for all grid-points in a grid simultaneously as a one multi-dimensional output from a single agent. Advantages: Single agent. Disadvantages: Only a few kinds of learners support this functionality: AdaBoost.MH, AdaBoost.MR, ML-kNN, Decision Trees, Neural Nets (BP-MLL), and some vector-valued kernel methods (possibly some SVM?). Of these, only Decision Trees (and associated types) and kNN have this multi-output functionality built in in scikit-learn.
Idea 5: Do some kind of stochastic ensemble on joined data (as used for Idea 2). Advantages: Parallelizeable. Agents and the ensemble get some notion of spatial relationships between points. Disadvantages: Many agents.
Idea 6: Train one classifier on Idea-2-like joined data, but do data reduction to reduce the total number of points. Possibilities: clustering, only training on points around boundaries, using representative subsets.