I was having a discussion with a friend of mine about some normal group properties and then came up with the question "if G is not commutative, then is there always a subgroup that is not a normal subgroup?" It's probably more easy to solve this in the following form:$$\forall H \leq G : H \lhd G \Rightarrow \forall a,b \in G : ab=ba$$ My question is, can anybody give a proof, or a counter-example (because I don't think it holds) of this theorem? Thanks!
The answer is no. The Quaternion Group provides the smallest counter example.
Another way to write your question is the following: "Does there exist a non Abelian group all whose subgroups are normal." Such counter examples to your above conjecture actually have a specific name, and can be completely classified. These are called Hamiltonian Groups.