Многие современные мобильные телефоны поддерживают проигрывание и запись1) файлов в формате 3GP. 
Этот формат разработан специально для применения в портативных устройствах с
небольшим разрешением экрана.

К счастью у нас есть свободный кросплатформенный конвертер видеоформатов ffmpeg 

В Debian GNU/Linux или Ubuntu поставить ffmpeg можно из репозитория. 
Версию для windows можно скачать по адресу http://ffdshow.faireal.net/mirror/ffmpeg/ 

Теперь перейдём собственно к конвертации: 

    ffmpeg -i input.avi -s qcif -r 12 -ac 1 -ar 8000 -b 30 -ab 12 output.3gp

Здесь ключи определяют: 
   -i input.avi - имя входного файла;
   -s qcif -r 12 - кодировать видео с разрешением 176×144 и 12 кадров в секунду;
   -ac 1 -ar 8000 - кодировать звук в один канал (моно) с частотой 
      дискретизации 8000 (это даст максимальную воспроизводимую частоту в 4000 Гц);
   -b 30 -ab 12 - установить видео битрейт 30 кбит/с и аудио битрейт 12 кбит/с;
   output.3gp - результирующий файл.

Кодирование идёт достаточно быстро и по окончании результирующий файл готов к отправке на телефон. 
Как перенести файл на телефон это уже личное дело Вас и телефона. На свой Siemens CX75 
я переношу файлы с помощью кардридера и RS-MMC карты на 512Mb. 

Хочу предостеречь от создания роликов большого размера. К примеру попытка проиграть 
на моём телефоне ролик в 17Mb (~50мин.) привела к зависанию и выключению тела.