How can we get gradient with some other loss function apart from MSE?
Yes we have. MSE loss function is usually used for regression problems. We can have different loss functions according to our needs. Follow the article below.
https://towardsdatascience.com/common-loss-functions-in-machine-learning-46af0ffc4d23
If you wish to learn as to what does gradient does in the algorithm   you can visit this article:
https://towardsdatascience.com/wondering-why-do-you-subtract-gradient-in-a-gradient-descent-algorithm-9b5aabdf8150