You don’t need to re-encode the video. Look up HLS segments, which is the standard for streaming video and I assume YouTube uses it.
Each video is split into many segments, like 10 seconds long (though the duration doesn’t matter). The browser first fetches a “playlist” which is just a list of these segments. Then the video player plays each segment in order. So Google could just insert ad-segments into the video stream, and if they did it cleverly, there would be no way to determine that they were ads.