?Pape mache? takes a while to produce & does not  bode well to touring & handling  - unless you have loads of tin lids (Kids) or students to do IT as an excise?
The quickest & easiest way using chook wire! Is  cover it in canvas or cheaper still unbleached calico (muslin). Add ?size? (wallpaper paste) if your are using a water based poster paint or pva wood glue in plastic paint. This will strengthen & retain the shape you have moulded the materiel into.  However mount it on a an mdf or ply board, so as to allow the materiel to be affixed & hold it?s original shape. As you said they are climbing over it, ensure an adequate wood support structure is under the wire & attached to the board.
Also you can use blocks of shaped Styrofoam shaped & covered & mounted the same way. The beauty of this is, it requires minimal building skills & will support being climbed over.
With the foam you may have to seal the surface or fix it to the material to stop it crumbling way - you can use the sized paint to achieve this, instead of buying a special adhesive.
 In both methods you shape the rock virtually as you apply the sized paint.
By using canvas type material - it can be repaired on the road by using a piece of ordinary roller bandage from the first aid kit & painted on as a touch up - rather than a messy Gaffer tape repair - that will always be seen for what it is!
Hope this helps you Andrea?

Andrea - Just a point on the use of Styrofoam & polystyrene!

It is produced from chemical contaminants. Fire, health & safety issues should be of a primary consideration & concern!
Check with your local Fire Service Marshal, as to local regulations concerning it?s usage, fireproofing &/or the required application of  fire retardants on theatrical sets & props.
Because of it's chemical nature it will perpetuate it?s own flame & give off toxic & potentially lethal gasses & fumes. Be aware of the dangers that can result from it?s usage, especially in theatre.
They are attempting to reduce the use of it here, as an insulating material, because of the residual effect if it is subjected to or in a fire situation.. In a fire it can revert back to it?s original chemical liquid form & become a molten fire accelerant.
So please check it out & the use of fire retardants/proofing in general - as good policy & normal work practice in theatre.

I am late to the game here, but having recently produced four papier mache trees, a boulder, and a stump I feel somewhat qualified :)

We started our project using traditional papier mache techniques, but switched to using fabric as a base quite quickly.  We were sort of making it up as we went along.

We found that creating a wooden armature of the basic shape (applied to a plywood base) covered with chicken wire.  The Chickenwire is fairly easy to staple to the wood, but wear gloves..  I then soaked muslin (only a dollar a yard) in a thinned white glue and molded over the top.  I used old sheets for some of the trees as well.

You want to be sure to leave a generous amount of fabric in the hollow places of your boulder. The fabric can be stapled down as well. The fabric will shrink somewhat as it dries.  It is a messy job, but the result is quite nice.  As to painting.  Use real boulders as a guide... you usually will need at least three colors if not four for good depth.  Greys, greens, mustards.... most boulders are not brown and neither are trees