Can a decision tree learn to solve a xOR problem?
Yes, a decision tree can learn an XOR.


  I have read online that decision trees can solve xOR type problems...


Often things are phrased not carefully enough.  A neural network can perfectly sort a list of integers, but training one to do that would be quite hard.  Your image shows that a tree can easily represent the XOR function, but your question is how to learn such a tree structure.


  My question is how can a decision tree learn to solve this problem in this scenario. I just don't see a way for any metric (Information gain, Gini Score, ...) to choose one of the splits in image 2 over any other random split.


Indeed, the first split is probably quite random, or due to noise (if you go for $\operatorname{sign}(x\cdot y)$ with continuous $x,y$ instead of the discrete $x,y$ and XOR).  But, as long as your algorithm makes the plunge with one of those first splits, the next splits are obvious and your tree will make them.


  Is it possible to solve the presented problem with a decision tree? 


Here's a notebook (github/colab, suggestions welcome) demonstrating that yes, a (sklearn) decision tree can learn $\operatorname{sign}(x\cdot y)$ (perhaps with some errors when points are extremely close to 0); but it also goes on to show some of the difficulties, e.g. when variables other than $x,y$ are available to the tree to split on.  Up-shot: noise variables can wreck that first split I mentioned above, and even useful variables can make the tree lose track of the XOR.


  Would using a random forest solve the problem in any way?


Probably not the basic problem, but it looks like it helps with, e.g., the noise variables above.