That palette switching trick always impressed me back in the day, although in practice I only ever saw it done every few character lines, not per byte as demonstrated in those videos. By my maths, a character line gets printed to a square-pixel (40 character wide) PAL display 400k times a second. The 6502 CPU, for example tended to run at 2MHz, meaning there were only 5 CPU ticks per screen byte, and when writing out a register takes at least 3 ticks, and keeping a counter capable of counting high enough takes 4 ticks, it's not really practical to change palettes on each character line on those old machine.
But a few games did switch pallettes a few times per scan, which gave you some pretty high-res graphics that looked colourful. And BBC Micro Elite even changed screen mode between the vector display at top and the console at the bottom - the vector display being done in square pixel monochrome mode, while the console was in 4 colour double-wide pixel mode - meaning the video memory was only the 10k you'd need for full screen mid-res two colour, while giving you a colourful multicolour console, leaving more RAM free for the complex game code.
What was also important about using low RAM modes was it gave you more time to run code - those ~5 ticks per pixel were halved if you tried to run a multicolour mid-res mode, because the video chip paused the CPU while it accessed the video RAM. Many games ran in 4 colour double wide pixel (low res) modes throughout, but Elite had a resolution boost over those.