Multi-threaded encoding of videos is very finicky, it depends entirely on the codec and encoder for availability--and Blender does not offer a lot of flexibility here. Part of the problem is that for a codec like h264, every frame must be provided in order, while rendering on multiple threads will inherently finish the frames out of order and would need to be kept around (stalling) or stored somewhere until the encoder was ready (caching.)
Fortunately you can use the Frameskip option along with multiple instances of Blender. You need to set Blender to render each frame to a png file, give it a directory to store the frames, then save a new Blend file so these settings will be available to other instances. Secondly, give each Blender instance a different starting frame (one from 1, the second from 2, and so on) with each having a frameskip equal to the number of instances being used. Each instance will render a frame to a png file, skip the Frameskip number of frames, and move on, until the video's frames are fully rendered. This may also be used to distribute the rendering process across multiple machines if need be. Do be warned that the speed of your hard drive also comes in to play here--too many instances will end up waiting on the hard drive before they can write another frame, not actually going any faster.
This method will get your video out of the VSE, however its not shippable yet. You would then need to use an encoding program (probably ffmpeg) to take the directory full of pngs and compress that to your file. Using ffmpeg at the command line is a lot less convenient than simply hitting export, however there is one major benefit: you get complete control over the encoding process in this way, including whether to use multi-threaded h264 support, and better control over encoding (Blender and even some commercial tools won't allow you to specify CRF settings).
