"I do not know how to handle terrain modifications without breaking
This is the crux of the matter, because you'll have lost the original source of information -- the conceptual material volumes painted on by your paintbrush -- as soon as you transfer it onto the 2D texture. So you'll have no volumetric reference from which to reconstruct your 2D texture UVs. This is where 3D textures become far more useful. But you don't need 3D textures as such, if you're willing to opt for a simpler painting process... just a 3D dimensional backing array that you'd use as a reference for where you've painted and where you haven't i.e. where certain materials lie beneath the terrain manifold. Unless you plan to use octrees or have a fairly tiny world, you'll probably want to make your "backing" data structure used for retexturing, quite low-resolution (relatively large cells).
Perform the paint operation in 3D space, with resolution equal to that of your quantised / voxelised "backing" 3D array. The paintbrush (also quantised / voxelised) will need to snap to these backing cells as you move it through space, in order for it to paint the backing array accurately. Your paintbrush might be of uniform colour, or every voxel (as opposed to texel) might be a different colour.
When time comes to (re-)construct, project from the each vertex, outward along the appropriate world axes, until you hit the implicit "face" of the backing cell into which this vertex falls. By sampling that point within the plane, you can get the UV for your terrain vertex (may require some averaging if you need to sample on multiple axes). I guess you'll also need to handle transitions somehow, i.e. where one triangle lies in one backing array cell, and the other two lie in (a) different cell(s). As these are rectilinear raycasts, and you will only be doing them in the locale of terrain changes, the cost over time will be negligible (and the majority of your level terrain will undergo this sampling as a pre-process before play begins).
(I'd suggest keeping your subject mesh simple to start with, as it may make things easier to conceptualise.)
The Real Deal
Alternatively, make use of 3D textures. You don't talk much about your intended paintbrush, so I cannot tell if you intend to use a 2D texture, 3D texture, or plain / uniform colour, for painting your terrain. Irrespective, this approach will work for all of the above.