Assume I have a MP4 video.
Can I rotate it by 90 deg WITHOUT re-encoding?
In future builds off the ffmpeg4x branch: yes (https://github.com/mean00/avidemux2/commit/c21e23dbdb932df702064e4977bf7a342944504a).
Assuming you use Windows, a 64 bits version thereof, you may want to try r190118 from https://avidemux.org/nightly/win64/
Of course, the new "Rotate video" setting in the MP4 muxer adds only a hint for video players to the metadata. The video stream as such remains unmodified.