CallRecorder Full 1.2.9 - WORKS PERFECTLY on Nexus 4 - records all calls - incoming and outgoing.
It is JUST a matter of settings:
- Device -> OTHER,
- Call record form -> Standard Android API,
- Standard API settings -> Audio source -> Default.

It records everything with above settings.

The real question is it possible to enable it somewhere in the settings - as in S3? Without installing any additional app?
Maybe MIUI ROM will have this feature... hopefully.

Also a Nexus 4 owner.
Nexus 4, Nexus 5
DEFY Green Lens