Are there "extremely non-commutative groups" $G\neq\{e\}$ such that $gh \neq hg$ for all $g,h\in G$ with $g\neq e$ and $h\notin \{e,g,g^{-1}\}$?
Note that if $G$ is both non-commuative and "extremely non-commutative" then every non-trivial element has order two or three (as $g^2, g^3\in\{e, g, g^{-1}\}$). Note also that there must exist an element of order three, as groups where every element has order two are abelian. Also, if $G$ is finite then it must contain elements of both order two and three, as otherwise the centre of the group will be non-trivial. So, the smallest non-abelian group with elements of order both two and three is $S_3$....
An example. The symmetric group $S_3$ is "extremely non-commutative". This is because centralisers of elements are cyclic: if two elements $x, y\in S_3$ commute then there exists an element $z\in S_3$ such that $z^i=x$ and $z^j=y$ (why?). The result then follows as all elements of $S_3$ have order two or three.
Infinite examples? There are no finitely generated, infinite examples of "extremely non-commutative" groups. To see this, note that (by the above discussion) $x^6=1$ for all $x\in G$. Therefore, if $G$ can be given by a finite generating set then $G$ is finite (this is non-trivial result, and the citation is M Hall Jr. Solution of the Burnside Problem for Exponent Six, Illinois J. of Math. 2 (1958), 764-786.) On the other hand, I see no immediate reason why there cannot be infinitely generated examples.
Classification of finitely generated examples. The only finitely generated non-commutative, extremely non-commutative group is $S_3$. This is because, by the above, such a group is finite, and so by user10354138's answer, the group is $S_3$.
Its worth remarking that the OP seemed unsure of what the definition of "extremely non-commutative" should be. I feel that the "correct" definition is that $G$ is non-commutative and that non-trivial elements have cyclic centralisers. Then, for example, every torsion-free hyperbolic groups satisfies this more general condition.
Original Answer: There are no nontrivial "extremely non-commutative group", because identity commutes with everything else. Of course, the trivial group is "extremely non-commutative" because the condition is vacuous.
Addendum: With the restriction $g\neq e, h\notin\{e,g,g^{-1}\}$ the question is more interesting. Certainly groups of order $\leq 3$ are extremely noncommutative (again, vacuously). Assuming order of $G$ is at least 4, $g$ commutes with every $g^n$ so you need every $g$ has order $\leq 3$. Since all groups of exponent 2 are abelian, you need some order 3 elements. For exponent 3 there are no examples, because every finitely generated exponent 3 group is finite (this is due to Burnside, On unsettled question in the theory of discontinuous groups, Quart. J. Pure and Appl. Math. 33 (1902), 230-238) and every finite $p$-group has nontrivial center. So you want a mixing of order 2 and order 3 elements, and $S_3$ is an example.
In fact $S_3$ is the only example of a finite noncommutative extremely noncommutative group, because such $G$ is generated by a Sylow-2 and a Sylow-3. The Sylow-2 can only be $C_2$ and the Sylow-3 can only be $C_3$ by the above discussion, so $G$ has order 6 and hence $\cong S_3$.
The centralizer $C(g)$ of some $g\in G$ always contains $\langle{g}\rangle$. For a group in which any $g\not = 1$ has this minimal centralizer, take $G$ to be free.