Is it possible to replace stock 'Phone' app? First of all, I know one can replace the dialer app and there are many options available for it. 
But is it possible to replace the stock phone app? Is there any calling app that uses the normal cellular network to make calls apart from the stock android app?

The reason why I am asking this is because I am having problems with talking on handset on my Nexus 5 since I update to Lollipop. And I figured that if I replace the phone app, this problem could be solved as my calls on Skype and Hangout are normal which proves that the microphone is fine and the problem lies in the software.
It might be easier on a custom ROM, as you can flash what you want. However, since you're on Stock, here's what I'll suggest.

Disable (uninstall) your phone app (if that's possible), then install another phone app of your choice. Automatically, that'll take over as your default phone app.