Encoding and muxing video using MediaCodec and MediaMuxer
The pixelation is most likely due to wrong frame timestamps, so make sure your frames' timestamps increase monotonically and are the same when you pass them to MediaCodec and MediaMuxer. In this specific case, you only need to replace the data for the frame you're going to replace, leaving its timestamp as it was in the original stream.
Make sure you're converting the bitmap to the YUV color space and you're using a correct pixel format. Android stores bitmaps in RGBA with 4 bytes per pixel, you need to convert this to YUV with Y value for each pixel and U and V values for a block of 2x2, then lay them out in separate planes in the byte array that goes into the codec.
Also, some time ago I made an example app that resizes videos using MediaCodec, it may help you as well: https://github.com/grishka/android-video-transcoder