We are accustomed to seeing chemical rocket engines that burn their fuel to generate thrust. There are many other ways to generate thrust however. Any system that throws mass would do. If you could figure out a way to accelerate baseballs to extremely high speeds, you would have a viable rocket engine. The only problem with such an approach would be the baseball "exhaust" (high-speed baseballs at that) left streaming through space. This small problem causes rocket engine designers to favor gases for the exhaust product.
Many rocket engines are very small. For example, attitude thrusters on satellites don't need to produce much thrust. One common engine design found on satellites uses no "fuel" at all -- pressurized nitrogen thrusters simply blow nitrogen gas from a tank through a nozzle. Thrusters like these kept Skylab in orbit, and are also used on the shuttle's manned maneuvering system.
New engine designs are trying to find ways to accelerate ions or atomic particles to extremely high speeds to create thrust more efficiently. NASA's Deep Space-1 spacecraft was the first to use ion engines for propulsion [source: SPACE.com]. See this page for additional discussion of plasma and ion engines.
For more information on rocket engines and related topics, check out the links below.