I've had great success printing with HIPS (high-impact polystyrene) as a support for both PLA and ABS. Most sites recommend it for use with ABS because the materials melt at similar temperatures and work best with heated beds, but I've had good luck using it as a support material with PLA on a bed at 60°C. It doesn't stick as well to PLA as it does to ABS, so supports tend to peel away very readily. The downside is that, if you need the support to anchor your print at all, it doesn’t really stick well enough to accomplish this task. For that, you must pair HIPS with ABS.
When you print with ABS or have complicated interwoven support structures, HIPS can be dissolved with D-limonene, a citrus based cleaner sold under various names like Citrisolv (others exist), or with dipentene (a mixture of L and D-limonene that doesn't smell as pleasant).
Regarding cost: I've found HIPS to be slightly more expensive than PLA/ABS, but only 1.5x the cost, not 4x like PVA. Additionally, it isn't hydroscopic in the same way as PVA so it lasts longer out of the package. Since you're using it as support, you also tend to use far less filament than you do for the main print (sparse support structures as opposed to solid print structures).
Water-soluble alternatives: There are a few proprietary blends of polymers sold by the big commercial printer manufacturers (3DSystems, Stratasys) that only work in their machines… these are generally soluble in basic solutions (water + sodium hydroxide or sodium carbonate). These are usually very expensive and you'd have to rewind the filament on a spool, as they come in cartridges made for specific printers. You'd also have to experiment with the right build conditions and solution blends to remove the material afterward. Airwolf has a support material called Hydrofill that purports to be soluble in plain water… I'm not sure how this is different from standard PVA, though I assume it is different. Hopefully more companies will work on developing water-soluble options to help us keep the 3D printing world full of renewable, less-environmentally-harmful options for filaments (both print and support).
Update:
Ultimaker now has a material called Ultimaker Breakaway. After using it for a few models, it works remarkably well, allowing me, for the first time, to print nice rounded surfaces on the bases of my prints. It really does just break away from the surface, much like HIPS but without the lack of adhesion problems between HIPS and PLA.