Is there any way to receive an update/new version released notification from the Play Store for an app that is not installed in my phone? I'm using 4.3 on a Nexus 4.
With Changelog Droid being currently "out of order"1, let me mention an alternative:
App Watcher claims to do the very same:
App Watcher notifies you about updates of applications from Play Store even the app is not installed currently on your device and provides quick access to the "What's new" section.
App Watcher (source: Google Play; click images for larger variants)
1: (according to a comment from winchendonsprings); by a response I've got from the dev, he's quite busy with other tasks at the moment, but did not abandon the app – he still plans to update it, but cannot give an estimate.