How to create textures on high-poly mesh?

I got a high poly mesh (~1.2mio faces, multires) and want to put a high resolution texture on it.
But somehow unwrapping wont work (blender & computer crashes).
Is there any other way, to paint a nice texture on this mesh?

I thought about vertex paint, but this doesn’t create a texture, as far as I know…