Hostmonster DOES allow ffmpeg to run... ffmpeg is what converts the videos to flv when you upload them. I think you are thinking of RMS, which no shared hosting is going to allow.. so you do need Cyberxing for that.
Sorry Mike, what you say is quite correct, RMS is not allowed on shared servers. but ffmpeg is ok. I have been using Hostmonster for a few years now, and their live support is excellent. I also use Cyberxing rms which I can highly recommend.
www.makeasocialnetwork.com/hosting/hostmonster