Styrofoam insulation stuff can be shaped easily, I have started building walls out of it. Also works great for rocks.
If you need ornaments you can use the rolling pins from greenstuffworld.com
Edit. Sniped, I have exactly that rolling pin.
Roll them over some putty or so, I use the (non toxic, BPA free) "fimo air basic". It is similar to clay and works great.
As a base for the scenery I have some hard foam sheets.