If G is not commutative, then is there always a subgroup that is not a normal subgroup?
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.