Die einzelnen Dateien werden zunächst mit avconv einzeln und verlustfrei in einen MPEG-Transportstrom umgewandelt und dann zu einer neuen MP4-Datei zusammengefügt:

avconv -i 1.mp4 -c copy -bsf:v h264_mp4toannexb -f mpegts t1.ts
avconv -i 2.mp4 -c copy -bsf:v h264_mp4toannexb -f mpegts t2.ts
avconv -i 3.mp4 -c copy -bsf:v h264_mp4toannexb -f mpegts t3.ts
avconv -i 4.mp4 -c copy -bsf:v h264_mp4toannexb -f mpegts t4.ts
 
avconv -i "concat:t1.ts|t2.ts|t3.ts|t4.ts" \
       -c copy -bsf:a aac_adtstoasc \
       output.mp4
 
rm t[1-4].ts

Für Debian/Ubuntu: apt-get install libav-tools