Stoned...
I think that having one or two of the figures turning to stone and maybe one of two actually stone is a great idea.
As for effect, you could do a marble and granite effect. Paint the stone parts or whole figure a medium, cold gray. Then take a crappy brush, and from a few inches away flick a black wash at the figure. It might take a few tries to get it right. Also, try other spot colors. Then, paint in some random, organic white lines. This will give the illusion of marble veins in the rock.
Another idea would be to use Vallejo\'s crackel medium mixed with gray paint over either black or white. This will look like the figure is kind of cracking apart.
Good luck!