"Can key frames be added without re-encoding?"
No, because the I frame is part of the coding. MPEG is a forward-encoding process, where the state of each frame is dependant on the frame(s) prior to it. This is why fast-reverse was such a pain in the butt on 1st generation DVD players. LD, on the other hand, excels at this, as each frame is independant.
