I've used ImageMagick's composite binary to watermark a JPG with a PNG image.
Like this:
composite -tile -dissolve 15 targetimage.jpg watermark.png
You can obviously use two JPEGs to achieve what you're looking for.
Using the -quality and -sampling-factor arguments will help retain quality. There is also a -compress <type> argument, where type can by Lossless. However, ImageMagick does not recommend the use of this value as the JPEG library must be patched to support this.
It's worth investigating though if it will achieve a genuine lossless image, and you're not happy with the quality of the compress and sampling-factor arguments.