How to speed up Blender Video Sequence Editor rendering?
Using only colored effect strips and a track of music, I rendered 240 frames resulting in the following export times:
H264 = 16 secs
MP4  = 14 secs
xvid = 13 secs

This tests only the encoding engine. I would also suggest checking the dimensions of the media you are editing with. Any scaling (which the VSE will do automatically) impacts on render time. Try to make this 1:1 with the scene dimensions. Further to the issue of scaling you may want to alter the AntiAliasing value in the scene properties as well. Default is 8 samples.

Finally, in User Prefs, increase the 'sequencer cache' value to maximise your memory usage. And check that you are using the Sound Output Device SDL, in the same panel.