The truth is that the rocket does have something to push against: namely, its own fuel. Let's illustrate with an example you kids can try at home. First, you need to get yourself into some sort of frictionless situation. Wearing ice skates on a slippery ice rink would be good, or maybe your office has a chair that rolls really well on a hard surface. Next, you'll need a medicine ball. You are the rocket and the medicine ball is your fuel. Toss the medicine ball. You'll notice that as you shove the medicine ball forwards, you yourself lurch backwards. Ta-da, the miracle of physics! (If you think this is because the medicine ball pushed on the air, then try the experiment without the medicine ball--just push on the air with your hands, see how far you lurch backwards.)
Newton's Third Law is usually expressed as, "For every action there is an equal and opposite reaction," and you can also think of it as "Forces always come in pairs." While you are pushing on the medicine ball, Newton's Third Law says that the medicine ball is also pushing on you. Thus, you are accelerated by the force acting (backward) on you by the medicine ball. Never mind that it was you who decided to start the pushing in the first place; you can't push on the ball without having the ball push back. Forces always come in pairs.
Of course, rockets work on more sophisticated principles than just tossing fuel out the back. First, the fuel is burned and its hot exhaust gases are expelled at very high velocity (if you toss the medicine ball faster, your body experiences greater backward force). And the rocket's exhaust nozzle has a narrowing so as to squirt the exhaust gasses out even faster, like putting your thumb over the end of a garden hose. Exhaust from chemical propulsion (i.e., fuel-burning propulsion) is typically expelled at 2 km/s (= 4500 mph), and your average rocket mass at launch is 80-85% propellant (fuel + oxidizer), most of which eventually gets squirted out.
Thus for example a Delta II rocket can send a 1800 kg payload into geosynchronous orbit, using about 200,000 kg of propellant. The total rocket at launch would have a mass of about 232,000 kg. That's a lot of fuel! This is because 2 km/s (= 4500 mph) is considered "low" speed in Rocket World, so you have to achieve thrust by squirting lots of mass. If you could squirt something even faster out the back of the rocket, you could get more thrust with less fuel, and therefore send heavier payloads.