I ran into the same issue with a cross platform port I needed to do with WebGL, WebPlayer, and other platforms that are unable to play videos in Unity. Unfortunately, the process is too involved to write your own implementation for each platform in Unity. Though it is possible.
After researching and going through the many assets for movie playback in Unity (I also needed to support video scrubbing), I came upon the AVI video playback plugin for Unity, which has ample support and works on every platform regardless of your settings. The greatest part of the plugin is it gives way more granular support than Unity's MovieTextures. It supports rewind, frame-by-frame step backward/forward, pause, fast forward, and looping. The only major drawback is that your videos have to be in the plugin's AVI format, and the plugin itself is slightly expensive (currently $49). I'd recommend waiting for it to be on sale, though the amount of time and effort you'll save will definitely be worth the price.
Here's the Asset Store link:
Here's the forum thread about the plugin as well: