With someone else mentioning Avisynth here in the comments (which is actually still used widely by video enthusiasts today), I became curious if there was a plugin for this sort of thing, and sure enough, I found Reformer[1]. With that, I figured I'd try reproducing OP's results. (By the way, while Avisynth is Windows software, as far as I know it works quite well under Wine).

Step 1: Download the video with youtube-dl. This gives us zelda.mp4 (original video) and zelda.m4a (extracted audio, requires ffmpeg)

    youtube-dl -x -k -o "zelda.%(ext)s" https://www.youtube.com/watch?v=rMXD5DxbXog

Step 2: Write the Avisynth script (in AvsPmod). Plugins used: LSMASHSource, Reformer, RemapFrames

    lwlibavvideosource("zelda.mp4")
    deskewed = q2r(last,"lanczos",60,90,51,412,588,148,581,417)
    normal = "[0 149] [1488 2063]" # frame ranges where to use original video
    ReplaceFramesSimple(deskewed,last,mappings=normal)

Plugins used: LSMASHSource, Reformer, RemapFrames

Step 3: Pipe it to x264 with avs2yuv (necessary under Wine and with 32-bit Avisynth & 64-bit x264) to encode the video.

    avs2yuv zelda.avs -o - | x264 --preset slower --crf 16 -o zelda.mkv - --demuxer y4m

Step 4: Merge encoded video and original audio back together with mkvmerge from mkvtoolnix. You could use ffmpeg here as well, but I find mkvmerge much nicer for simple muxing like this.

    mkvmerge -o zelda_muxed.mkv zelda.mkv zelda.m4a

And with that, we're done. The whole process took about 20 minutes (of which ~13min was spent encoding the video) and a few hundred megabytes of space (since there's no need to have all the frames as individual image files several times over). Other benefits include having the video run at the original framerate of 29.970 (OP's video runs at 25.000 since he forgot to set the framerate when encoding the processed images), including the audio as well not having distorted picture when the TV isn't visible (which was simple enough to do with the ReplaceFramesSimple function from RemapFrames). You can see the end result here:

https://www.youtube.com/watch?v=Jk_z4TiweHs

[1] http://www.avisynth.nl/users/vcmohan/Reformer/Reformer.html