Is it possible to change the brush on the vertex paint option?
Yes, you can use textures to serve as a brush. Here's what you do.

Make or find a brush texture. I quickly drew one in GIMP. As far as I know, the color of the brush doesn't matter, just the alpha channel. That means you can play with brushes that fade towards the edges, etc.

In the texture panel, add a texture as an image and assign your brush image to it. Make sure Use Alpha is checked! See image below:

Now you have a texture available that will serve as a 'brush'. Back in the uv editor you can start painting. Expand the Texture panel below the brush settings and click on the big checkerbox button. Select your texture and you'll be able to paint using the texture as a brush. Note the Brush Mapping drop down. In the image below, I used Tiled, View Plane, and Random. I assume you'll probably want View Plane to start.


Two cool things:

I like the Rake feature. It will rotate the brush depending on the direction you're painting. Awesome!

I haven't tried this yet, but you could probably paint a texture in Blender and then use it as a brush. Now that's Meta!

P.S. I made this fur texture thing using that brush (for demonstration purposes)


P.P.S I am not a texture artist.