What you need is exterior masonry paint.
Which specific kind of exterior masonry paint may depend on what sort of stone you're using. This page from a decorating advice site tells you which kind of paint to use in which context. It's written from the point of view of painting walls of a building, but some of it may still be useful to you.
In particular, mineral-based or lime-based paint should fit your criterion of being eco-friendly, and limewash looks like the best choice for your situation: it's simple to make, relatively cheap, looks natural, and is eco-friendly. The following quoted text taken from the above link even provides you with possibilities for where to buy it:
Mineral Based Exterior Paints
Put simply, mineral paints are made with a silicate binder which reacts with the surface of the wall to form a long-lasting bond, unlike traditional paints which simply form a skin. They are naturally alkaline, so inhibit mould growth and carbonation; mineral paints also have the added advantage of being eco-friendly too.
The disadvantage is that they require more thorough preparation, special primers and are, initially, much more expensive – although the increased performance should pay back over the long term.
There are a few specialist manufacturers of mineral based paints – the main two being Keim and Beeck.
Each have their own detailed specifications for different kinds of wall surface and these must be followed to the letter in order to enjoy the maximum performance.
Lime Rendered Walls
For old buildings with a lime based render or lime based pointing a traditional Limewash is ideal. Limewash is simply a paint made from lime powder and water together with a colourant.
The main advantages of limewash are they bind to the surface very well and are totally breathable – another benefit is that they are relatively inexpensive.
Care needs to be taken with application and sometimes additional binders need to be added to aid adhesion.The finished result can be very striking though – looking much more natural than a traditional paint finish.
Limewash paints are available from a number of sources including Ecos, Ty-Mawr, Little Greene and Farrow & Ball.
ECO Paints
Technically, an ECO paint is simply a paint which has a very low or zero volume of Volatile Organic Compounds. While some ECO paints are obviously superior to others there isn’t any case for suggesting that an ECO paint will perform any better or worse than any other form of exterior paint – it will simply be a matter of personal choice.
It’s worth noting, however, that mineral and lime based finishes, mentioned above, are by their very nature eco-friendly – so would make a good choice if you wanted to be as environmentally friendly as possible?
I also found
detailed instructions on how to repaint a gravestone. They recommend using oil-based paint, assuming a granite headstone. If you're thinking more along the lines of smaller stones or pebbles, then
this site recommends using acrylic paint, with a sealer on top at the end.