avconv (als commando, doe maar eens "man avconv", is het er niet installeer het dan)
avidemux
vlc
transcode
ffmpeg
etc.
mp4 is een container-formaat. Het formaat van het de video moet daarin nog gekozen worden
Bv. divx,xvid,quicktime etc. (en ook de audio, dacht ik)