>In the general sense, is out-of-distribution learning even possible?

Yes. Humans can learn to answer questions even when questions (test cases) don't come from the same distribution as the training set.

You need to have some amount of analytical capabilities. Analytic as the ability to form distinct and modular concepts from the input and form representations that can be composed together to generate instances that don't exist in the distribution. The low-level example of this ability could be blind source separation.