I don't have an iPhone anymore, but back when I had one, I made a little script to do just that.
Here it is :
if "$1" == ""
echo This script this script takes a video file as parameter, and tries
echo to convert it to MPEG-4 in an iPhone-compatible format.
echo A file list, or wildcards caracters can be used as parameters.
for file in $@
ffmpeg -i $file -f mp4 -vcodec mpeg4 -maxrate 1000 -b 700 -bufsize 4096 -g 300 -acodec aac -ab 192 -s 480x320 $file.mp4
You can copy it and paste it as a new text file. Then make this file executable (chmod +x [filename]) and run it from the commandline, with the source video file as parameter (multiple files can be put as parameters, for multiple conversions, and wildcards are accepted).
The resulting file will be named the same as the source, with the ".mp4" extension added to it.
Looking at it, it seems you only need ffmpeg to use it. Maybe some codecs also, but I guess you have them already if you already played with video conversion :)
If you don't already have it installed, try :
sudo apt-get install ffmpeg
Hope this helps.