Fuel contains potential energy. When burned/consumed, that energy is translated into momentum in all directions. If a rocket directs the momentum of the gas resulting from burning fuel in one direction, the rocket itself must gain momentum in the opposite direction since momentum is conserved. The atmosphere does not really play a role in this process (other than providing resistance against the rocket).
Here is a picture illustrating the situation:
At $t_1$ the rocket is hanging still (total momentum $p(t_1) = 0$) in vacuum. At $t_2$ the fuel has been ignited and expands (explodes) in all directions. Since it can only expand freely out of the bottom of the rocket, it gets a net momentum $p_2$ out of the bottom. By conservation of momentum
$$0 = p(t_1) = p(t_2) = p_1 + p_2$$
the rocket must gain $p_1 = -p_2$ such that the total momentum is still zero. The physical force $F = dp_1/dt$ acting on the rocket is the gas pushing against the walls containing it. The two side walls cancel, but the force acting on the top wall is not counteracted by anything.
I do not see how pressure gradient force is related to the question. This is also how a rocket functions inside the atmosphere.