ffmpeg comes with a tool to re-order the MP4 “atoms” (Seriously don’t ask what are MP4 atoms it’s geek for the sake of geek).

find the file in ffmpeg_src/tools/qt-faststart.c

compile with gcc

gcc qt-faststart.c -o qt-faststart

And run.

/path/to/qt-faststart /path/to/src_vid.mp4 /path/to/output.mp4

NOTE: This only seems to work for h264 encoded videos (libx264).