ls | cat -n | while read n f; do mv "$f" `printf "video_%03d.mp4" $n`; done

video_001.mp4
video_002.mp4
video_003.mp4
and so on...

i=1; for file in *.mp4; do mv "$file" $(printf "video_%03d.mp4" "$i"); i=$((i + 1)); done