I have come up with a couple ideas for engraving or etching non uniform surfaces.

1st is probably the easiest for individual projects. Cut a stencil and then abrasive blast the surface. Probably a similar idea to putting on a protective coating and then acid etching.

Here is another. Obviously it would not work for grossly irregular surfaces, but maybe for a slightly curved surface. Mount a spring mounted platform on your mill or router table. (designed with guide pins to keep it relatively level as it goes up and down.) Secure your curved object to the spring table. Set Z for the lowest surface you intend to engrave. Obviously it would depend on the hardness of the surface to be engraved and the spring pressure holding up the table. Still it seems like it might be simpler than trying to rotate the object in a 4th axis if you do not have exact math hand to map its surface. I was thinking this might be cool for engraving the sides of a pocket knife or something like that as gift or momento items for limited production.