When you fire a gun, you feel recoil, because the momentum imparted upon the bullet must have an equal and opposite momentum imparted upon the body of the gun itself. In short, you pull the trigger, the tiny bullet shoots forward, and you and the gun together as a single system gain an equal momentum distributed over the far larger mass pushing you backward.
A rocket operates on the same principle, except in reverse. Instead of applying force to the gun as a side-effect of applying force to the projectile (the bullet), you apply force to the projectile, in this case exhaust gases, as a side-effect of applying force to the rocket. The gases shoot downward with a momentum equal and opposite to that of the rocket, which shoots upward, assuming you're trying to get your rocket to space, that is.
This loss of exhaust mass is what allows a rocket to move, without which you would be correct, and there would be some difficulty explaining the motion of the rocket within the confines of Newtonian mechanics.
As for frame of reference, you can attach your frame to the rocket itself, in which case you have an inertial frame of reference that needs to take account of the loss of mass to the exhaust. Or you can be a bit more adventurous and attach your frame to the exhaust gases, which is valid if done for small slices of time, but far more difficult if you want to account for the total length of time the rocket is in motion. Or you can attach your frame a point in space where the rocket is at a given motion, and you'll notice two equal and opposite momenta being applied to the rocket going one way, and the gases going the other, though clearly the gases will be traveling at a much higher speed. Up to you as to how far you want to take it!
Finally, to address your last question, your empty universe starts out with a rocket, complete with the fuel that it will then burn and expel as exhaust gases. These gases don't disappear from the universe as soon as they leave the rocket, and you're left with an almost empty universe, containing a rocket, and a bunch of fast-moving gas. That's what you're missing.