Zbrush has a special mode for painting an object!
It's the "polypainting" mode http://www.zbrush.info/docs/index.php/Polypainting

It's the more easy, you have just to paint on the surface of the object
It's better if you export your model with big numbers of polys (for have not to subdivise in Zbrush)
from Moi in "Triangles Only" format Obj