Understanding minimizing cost correctly
Consider differentiating this $$\nabla_\theta\|X\theta -y\|^2=2X^T(X\theta -y)=0$$

Hence solving this, would give us $$X^TX\theta =X^Ty$$

Solving this would give us the optimal solution theoretically. However, numerical stability is an issue and also don't forget computational complexity. The complexity to solve a linear system is cubic. 

Also, sometimes, we do not even know even have a closed form, a gradient based approach can be more applicable.