Use Vertex Paint mode to color the sculpt. To make the vertex colors renderable set the nodes as pictured below (add the Atribute node with the vertex color's name and use it as a Diffuse color). There are some limitations in this method though- you have the access to only few brushes (compared to the ones available in Texture Paint mode) and the sculpted mesh should be very dense if you want to paint some detailed strokes.