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.
There isn't anything built in but you can use an app such as Changelog Droid. You would need to add the apps you wish to be notified for to the Observed list within the app.
Note: It appears this app is no longer being maintained and has problems with paid apps. I do not know of an alternative at this point. This app will still work ok for free apps though.
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.