Re-encoding is difficult but you don't necessarily have to do that. As far as I know it's possible to just splice segments of video between "key" frames without otherwise re-encoding the full video.

YouTube already re-encodes every uploaded video into multiple formats; it would be possible for them to develop a "smart" encoder to be aware of the visual content of the video in order to place "key" frames at natural breaking points of the video, such that subsequent ad insertion would be semantically correct and not too jarring.