How to record my calls on Nexus 4 with Android 4.4.2?
Try Easy Voice Recorder. It works for me (Nexus 4, Android 4.4.2 without root). 

When you have root privileged, it is much easier. But without root, I don't know any apps that can record the other side in a way that you can hear him "clean". But as I said, Easy Voice Recorder did a very good job for me. Not perfect (crystal clear), but good (I can here the other side in the record without any issues).