I've twice rotated .mp4 format video with success using Sony Vegas software - but of course the resultant output was square format. I am sure that other products will allow this too but I have no experience of them.
The need to rotate each frame was the same as yours but at least we have some output rather than none - and there were only a few frames with heads chopped off. The rest looks passable as amateur video.