Is there any way to resize an mp4 video without reencoding it?
I plan to do this in Ubuntu Linux 12.04 x86_64.
No, you have to re-encode it.
Most video codecs work with so-called macroblocks of pixels, thus they are bound to a very specific pixel size. If you had some way to easily change the pixel size, then all mathematical operations that were done during encoding would become useless.
These mathematical operations, for example, include the distance between certain macroblocks – and since this is measured in pixels, you can't just change the pixel dimensions like that.