Question 1
Since you have asked us to assume that fair use does not apply (a big assumption!), your question hinges on "copyrightability." In the United States, one requirement for copyright protection is that the material have "at least a modicum of creativity." (That comes from Feist, a Supreme Court case about the uncopyrightability of the white pages of a phone book.) The standard line is that facts aren't copyrightable, only expression. Relatedly, the scènes à faire doctrine eliminates copyright protection for tropes and conventions, and the merger doctrine eliminates copyright for very simple expressions of facts. A selection or arrangement of uncopyrightable components is copyrightable, so long as there is creativity in that selection or arrangement.
Here's an example from the Compendium of U.S. Copyright Office Practices (2017):
The Office may register a work comprised of rocks that are selected, coordinated, arranged, and fixed in such a way as to result in a sculptural work. Likewise, the Office may register a photograph of a rock, a drawing of a hand-tool, or a written expression of an idea. However, the Office cannot register a mere “compilation of ideas,” a mere “selection and arrangement of hand-tools,” or a mere “compilation of rocks,” because ideas, handtools, and rocks do not constitute copyrightable subject matter under Section 102(a) of the Copyright Act.
If you use only uncopyrightable components of the original and do not copy a creative arrangement of those components, then you do not need permission (nor do you need to rely on fair use). This is simply something copyright permits, without permission from the rightsholder in the original work.
I've based my answer on U.S. law, which is my expertise, but this concept of copyrightability has equivalents in every copyright regime. The details, including the threshold of copyrightability, do vary significantly. For a slightly more international perspective, you might want to check out Copyright for Librarians, Module 3: The Scope of Copyright Law.
So, the answer to question 1 is, "it depends." Sometimes yes, sometimes no. (A lawyer's answer, I know. Sorry!)
Question 2
As for question 2, rotating a 3D graph, I disagree with the assessment that that's "OK," but perhaps I'm misunderstanding. Certainly reproducing a 2D graph with a 90 degree transformation would implicate the reproduction right. Perhaps what is meant with the 3D graph is such a rotation as to require creation of new material (e.g., showing only the side that wasn't visible).
Question 3
Certainly it is "legit" if it doesn't involve copying copyrightable material.
Question 4
Whether to cite the original depends on what your version looks like, as well as the norms within your discipline. In the U.S., citation is not a matter of copyright law. In countries with stronger moral rights regimes (virtually all other countries), attribution can be a matter of copyright law, but if your new figure only uses uncopyrightable components, that still shouldn't be an issue.
Expertise: I am a U.S. lawyer who works in an academic library teaching faculty, staff, and students about copyright law.