Yes, this seems possible. Go to Appearance -> Basically Theme Options, and choose the Layout Options tab along the top. Choose the middle layout, the one with left-hand sidebar, and ‘Save Changes’. This gives you a left-hand sidebar area, which you can add a menu to.
First, create your desired menu under Appearance -> Menus, and then visit Appearance -> Widgets and drag a ‘Custom Menu’ widget to the General sidebar area. Be sure to choose your previously created custom menu for the Custom Menu widget’s options, and you should have the desired left-hand menu.