I don't think there's a way to do this. I have an original iPhone running 3.0 and my wife has a 3GS, and I couldn't do it on either. It sounds like an oversite by Apple. Maybe this will be resolved in a future update.
I even tried sneaking a file in through iTunes, and it didn't show up (on my original iPhone), although it may work on a 3G or 3GS. I added a .mov to one of my photos folders that is usually synced in iTunes. This was a video that was recorded on a 3GS, so I know the file is OK. This is a lot of work to get a downloaded video file onto the iPhone. Like I said, it didn't work on my original iPhone, but let me know if it works on 3G or 3GS.