Is it possible to record a video as avi or mp4? I've recently bought a Motorola Milestone 2 (Froyo) and I see that when I record a video it produces a .3gp file.
Is there a way to have it produce an avi or mp4 instead? Would I have to root the phone?
Root won't be necessary, the Android API allows Apps to set the output file format to .mp4. So you just need to find an App that makes use of it. 

But, as with most video file extensions, .avi and .mp4 are just container formats. Therefore the actually used video codec, that is responsible for the quality of the video, isn't changed by changing the container format. The Android API itself recommends to use .3gp as container format for better compatibility.


  Using an MPEG-4 container format may confuse some desktop players.


Source

I'm not aware of an Android video recording app that actually saves the video with H.264/AVC compression. I think that this is because of the royalty fee one has to pay to use the codec.