How to remove exif from a JPG without losing image quality?

Having made similar changes to MIME types in file headers that were incorrectly stored, I'd suggest you verify the length of the EXIF data via the standard tools, and then "Zero" the data manually using multibyte string functions.

EXIF can only be a maximum of 64KB in a JPEG file, however I'm not positive if it's exacly 64KB, so I would begin with this.

Consider keeping the ICC profile (which causes richer colors) while removing all other EXIF data:

1. Extract the ICC profile
2. Strip EXIF data and image profile
3. Add the ICC profile back

In PHP + imagick:

$profiles = $img->getImageProfiles("icc", true);

$img->stripImage();

if(!empty($profiles))
    $img->profileImage("icc", $profiles['icc']);

(Important note: using the ImageMagick 3.1.0 beta, the result I got from getImageProfiles() was slightly different from the documentation. I'd advise playing around with the parameters until you get an associative array with the actual profile(s).)

For command line ImageMagick:

convert image.jpg profile.icm
convert image.jpg -strip -profile profile.icm output.jpg

Images will get recompressed of course if you use ImageMagick, but at least colors stay intact.

Hope this helps.