How to re-encode video without losing quality
The first option isn't a possibility. The second one, however, is. You should be able to de-multiplex the audio and video track and then re-package new audio with the video. FFMPEG is the program that I tend to use for this kind of task, but you'll need to be comfortable working from the command line. Depending on the OS you use, there may be easier tools for this.