"For a superuser command-line approach with more control, FFMpeg will do this. You can find all of the more advanced tweaking options here. A basic conversion would look like so:
ffmpeg -i myfile.avi -target vcd /tmp/vcd.mpg
For a GUI Avidemux is great:
Both are free and open source, don't think it gets any less restrictive than that."
"use media-convert.com it works very well, but the downside is its online. VLC can also do it, but I'm not exactly sure how. (its got to be a very recent version of VLC)"