This is only possible for lossless video codecs. Many of those store the video data pixel-by-pixel, mostly in the YUV colorspace. It would be pretty easy to edit such a video because you know where every position is located, and you can simply overwrite parts of the bitstream without consequences to the remaining stream. Even if the lossless video was compressed (in the arithmetical sense, without losing data), you could uncompress it first and then edit—no problem with that.
So, 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 again. Or, if you have a lossless x264 video in an MP4 container, you could edit it, and encode it to lossless x264 as well. In that case you'd have to decode the video first though, because a H.264 bitstream is not as easily accessible as a raw YUV stream.
For any lossy video codec, this is impossible though. The problem is that the 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 a 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. 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.
So, unless your video is lossless, and you can store it losslessly, you can't edit a video in-place without sacrificing quality.