Here it a nice tool (easy-to-use script) to download videos from Youtube: youtube-dl.
The new videos (since 2008) are coming using the H.264 video standard, that means you don't need to re-encode those videos into mp4, you just need to change the container, and that is pretty easy to do! :)
ffmpeg -i input.flv -vcodec copy -acodec copy output.mp4
If the video does not come in the H.264 video standard, than you will unfortunately need to re-encode it, and lose quality in the process. :(