How to make VSE render faster?
Update:
Multithreaded VSE rendering is now natively implemented in blender (since around 2.8 or 2.9), which makes this project kind of obsolete, but for more fine grained control of resources (background rendering, utilizing multiple machines) it can still be useful.

tl;dr: Open source program for automated solution is at the bottom of the post. Latest release as well as usage instruction can be found at the GitHub project page:

Problem
I was looking for a free (and maybe even open-source) video editor, and after using it for a while I found out that Blender is very capable of this task, but I was facing the same problem with the unused resources during exporting the finished file. I was searching everywhere, but I couldn't find anything about speeding up the Video Sequence Editor (VSE) rendering that would work for me.
Solution
After thinking for a while and trying out things I realized that I can run multiple renders at once from the command line, and it seems like the performance scales pretty much linearly with the number of instances running. Of course until you reach the limit of your processor or the amount of RAM you have. (I was running at 87% CPU and 89% of the memory filled, and I wouldn't recommend going higher, because if one of the rendering processes fail to allocate more memory it will crash and you have to do that part over again.)

After you have the parts/chunks of rendered video, you can put it together using the concatenation functionality of ffmpeg. I tried it with mp4 [H.264] and avi [Xvid], so I can confirm that those are working, but there might be other formats that can be used, but I haven't experimented with those yet.
Code parts
I don't have time to do a full tutorial now, but if anybody will show interest I might get around to putting together something.
For this to work you need to have the blender and ffmpeg executables in your PATH environmental variable, and the project file needs to be in the current working directory of the command window.
The code parts I finally ended up writing and using were these:
blender -b &quot;name_of_project.blend&quot; -E BLENDER_RENDER -s 0 -e 1000 -a

to render one chunk of video. (You can try changing BLENDER_RENDER to CYCLES if that works better for you, and you have to replace the 0 and 1000 with the actual frame range you want to render. I had quite good results with doing it in chunks of 1000 frames and having around 4-6 processes running at once.)
You have to have multiple CMD windows open at once (unless you write a program to automate it), and you need to call them with different frame ranges.
(I would suggest 0 - 1000; 1001 - 2000; 2001 - 3000; ...)
[The frame range is inclusive, so pay attention not to write the ending number as the beginning number for the next process.]
You have to set the output properties in the Blender rendering setting while the project is open, but you can close the window afterwards. I think you can also set memory limit for the individual processes in Blender at File -&gt; User Preferences -&gt; System -&gt; Memory Cache Limit, but I am not entirely sure about what that does.
For generating the list with the filenames I used PowerShell:
dir -n *.mp4 | %{&quot;file '&quot; + $_ + &quot;'&quot;} | Set-Content parts.txt

And for joining them I called ffmpeg (also from PowerShell, but this should work from CMD too.)
ffmpeg -f concat -i parts.txt -c copy ../output.mp4

This seems to be almost instantaneous, so you don't even really need to count this into your rendering time. It puts the resulting video in the parent directory so it doesn't get mixed into the video parts.
(If you used avi, you only need to change the extension of the output file and this should work.)
I hope that I could help somebody!
Sources
My main sources for the Blender command line options were these sites:
https://www.blender.org/manual/render/workflows/command_line.html
https://www.blender.org/manual/advanced/command_line.html
http://wiki.blender.org/index.php/Doc:2.4/Reference/Command_Line
And for the joining of the files using ffmpeg:
https://trac.ffmpeg.org/wiki/Concatenate
https://superuser.com/questions/607383/concat-two-mp4-files-with-ffmpeg-without-losing-quality/607384
https://stackoverflow.com/questions/15186500/howto-merge-two-avi-files-using-ffmpeg

Edit 2:
Version v0.4 has been released with the contributions of RedRaptor93.
Edit:
Program
I wrote a very basic application for the purpose of automating this process, that GitHub user MeTwentyFive very generously took upon and updated, so now it's more convenient and less buggy.
I have the code of that publicly accessible here:
https://github.com/Isti115/BlenderRenderController
I also included an executable in the release of the package, but for that to work you need to have the main blender.exe file accessible from the PATH environmental variable for rendering, and the same thing holds true with ffmpeg.exe for concatenating the parts.
If you need any help modifying, compiling or using it then feel free to message me!
ps.: You can get ffmpeg from here: https://ffmpeg.org/download.html
And I assume that you already have blender, since you are here asking questions about it. ;)

Edit 3:
Mikeycal Meyers wrote his own python script as a cross-platform solution for the problem.
You can find his explanation about it here:
https://youtu.be/rgwP5L1bICk
and the actual project here:
https://github.com/mikeycal/the-video-editors-render-script-for-blender
Make sure to check his work out as well, and help him improve it if you know some python! ;)