Ultimately, you need an h-bridge driver of some sort to control the motors fully (to be able to vary their speed with PWM, and change their directions). There is no way around this. But there are cheaper ways than an Arduino motor shield.
The standard shield uses two L293 (or equivalent devices). You could, for instance, purchase a couple of those, a breadboard or perf/veroboard with plated holes, plus a few other parts, and build one yourself. If you shop all surplus (and/or Ebay), you can do it for only a few dollars (plus your time).
Another alternative would be to use an L298-based driver board; you can find those cheap (again from China) on Ebay - I've seen 'em as low as $5.00 USD each in single quantity - and they may even be cheaper than that now (in multiples, you can get 'em as low as $2.50 each). You'll have to run wires and such from the Arduino to the controllers, but you wanted cheap.
I don't recommend using the L298 for homebrew boards unless you like a real challenge; the L298 has a weird pin spacing that isn't compatible with most (all?) 0.1" hole-spacing perfboards or breadboards, and without an adaptor board (which you can purchase - see this guy: http://www.jrhackett.net/index.shtml - he also sells a PCB for the L298 which you have to supply your own parts to complete; check it out!) they are very difficult to work with. Not to mention how it is nearly impossible to find a Multiwatt form-factor heatsink...
Another possibility would be to wire up your own small transistor h-bridge:
You can buy the transistors surplus (if you can, use both NPN and PNP transistors for the h-bridge; it's more efficient than an all NPN design, like the above link shows). Here's some more info:
http://letsmakerobots.com/node/9450
Just start googling "h-bridge", "transistors", "small", "2n2222", etc - you'll find plenty of designs, and since these small signal transistors are a dime a dozen, you can afford to experiment and blow a few. Here's another great design:
http://library.solarbotics.net/circuits/driver_4varHbridge.html