Collision resolution was indeed a nontrivial problem to solve, but I find it satisfying when I finally manage to solve that kind of problem.
My solution was to simply incrementally move the player, pixel by pixel (first horizontally, then vertically) and check for collisions in each iteration. Also, in the collision resolution I gave the highest priority to pushing up, then to pushing along x axis and lastly to pushing down. That was in order to make the player movement mechanics less frustrating to the player in most cases (i.e. player has a greater chance of "squeezing up" instead of unintentionally/unexpectedly hitting the head when trying to make a jump).