В этом поможет любимый mencoder:

$ mencoder input.avi -o out.avi -of lavf -oac copy -ovc lavc -lavcopts vcodec=mpeg4 -vf scale=420:-2

Здесь указан размер только горизонтальной (стороны -vf scale=420:-2), вертикальная изменится автоматом пропорционально