This is only (practically) possible for lossless video encoding.
Lossless to lossless
It's very simple to do what you want for losslessly encoded video codecs. Many of those store the video data pixel-by-pixel, mostly in the YUV colorspace. Also, every frame stands on its own.
It would be pretty easy to edit such a video because you know where every frame is, and where every pixel position is in the byte stream. You can simply overwrite parts of the byte stream without consequences to the remaining stream. Even if the lossless video was arithmetically compressed, you could uncompress it first, edit, and then compress and save again—no problem with that.
So, for example, if you have a raw YUV video in an AVI container, you could edit it on a frame-by-frame basis and save it to YUV in AVI again.
Keeping the lossy encoding
But if you want to do lossy video encoding—or keep the original lossy encoding—after the editing step, this is impossible. There are two problems with that: the encoding process itself, and the fact that often, frames depend on each other.
Lossy compression tries to remove redundancy as much as possible, by removing details the human eye doesn't see. This is done in several steps, but the most important one involves transforming the pixel domain into the frequency domain, often with variants of the Discrete Cosine Transform.
What this step does is that it takes a block of, say, 8×8 pixels and transforms it into a block of frequency coefficients. From this block, certain coefficients are dropped, which reduces the amount of information (and thus compresses the size), but also throws away visual information, which reduces the quality of the video. Which coefficients are dropped depends on the quality setting of the encoder. The video is then not stored as pixels, but as frequency coefficients.
When you want to edit a lossy video, you first have to reconstruct the frequency coefficients into a pixel-by-pixel representation again (like mentioned above). At this point you could edit the video, and insert a logo, but once you'd want to store it again, you'd have to perform the transformation step again—and throw away information. This is, in essence, the main cause for generation loss.
Another problem is the fact that for most lossy video, some frames depend on the information contained in other frames. More specifically, B- and P-frames only contain offsets of earlier (or later) B/P or I-frames. If you changed the contents of an I-frame, all the other dependent frames would change when they are decoded, which is typically not what you want. Peter Cordes' answer below hightlights this point. And indeed he's right that in principle, you could edit a lossy I-frame only video in place, but it would be practically very hard to accomplish.
So, very simply speaking, unless you can store a video losslessly, you can't edit a video in-place without sacrificing quality.