The problem you have is indeed probably because the video you want to put on is in a format the iPhone/iTouch/iPod doesn't support. You'll have to convert it or have iTunes convert it. A good tool for conversions is 'MediaCoder' or 'MediaCoder iPhone Edition'.
If you hate iTunes as much as I do, then you should give 'SharePod' a try. That's what I use to put stuff on my iPhone. You need to have iTunes installed because it uses some of its sys files, but you never have to fire up that mind numbing p.o.s. called iTunes again.
Good luck