Is your game deterministic? If it is then you should be able to record user input. Then to play it back you just run the game and provide the recorded input instead of live input.
Depending on the type of game the hardest part will be making it deterministic. You will need to capture all seeds to random number generators and how many times you have gotten a number from the generator so that you get exactly the same results out. Since we are talking about a single core you don't have to worry too much about order of evaluation which is good, but make sure it is well defined.
Second it will be easiest if you use a MVC(model view controller) setup then all you need is a playback controller and a live user controller that records timestamped input if necessary. Note: depending on how you do it it may be easier to use a frame count rather than an actual time. When the player hits record, gather the entire state of the game, and start capturing player input.
To export video all you have to do is load the starting state playback a frame, capture the frame then iterate over the entire playback record. If you have things in your game that are time based you will have to fiddle with the clock so that time spent doing the video capture is removed. Alternatively you could record time based events with a frame count so that it happens at the right frame, but then you have to make sure the different processing order doesn't change the game.
A second option is to go event based, just record every event that happens in the game Then during playback just trigger those events during the frame they originally happened in. This requires capturing more data since you aren't using the game to simulate everything(you still need to do animations and such), but might improve render times as you aren't running the whole game.