If you've got MP4 videos, then you don't want to stream them, you want to pseudo-stream them. There's a difference between streaming and "pseudo-streaming" which is what's called progressive downloading, allowing a user to watch content as it's downloaded rather than waiting for it to load.
What you're looking for is a program to put the video meta information at the beginning of the file, rather than at the end (which is why the video can't start until that piece is downloaded, the very last piece of the file).
There's an Adobe AIR program called QTIndexSwapper that will do this for you:
Run your video file through that and it should automatically progressively download.