That would mean reencodingevery video for every user and would need an insane amount of computing power.

You actually don't have to, on account of how adaptive video streaming works. It's fully possible to serve a few segments of ad content mid-stream.