Research suggests that I have to completely remake my wordpress theme to do this?
Your theme is actually well designed for a minimum 1024 X 768 resolution, which is the standard these days that most web designers aim for. There isn’t really any extra space if you resize your screen to mimic that resolution. If you put another sidebar there, then it will be cut off for all the people viewing your site at that resolution.
If you want to add a sidebar there nonetheless, you’ll need to rejig your theme’s CSS and PHP/HTML files.