I had a chance to install Facebook Messenger on a colleague's Nexus 4 (he didn't have it previously installed, nor does he have a Facebook account) and lo and behold, I was able to sign in with my own credentials.
So I thought I'd format my Nexus, start fresh and install Facebook Messenger before I installed anything else, including the Facebook main app. Well, I STILL GET THE DAMN SOMETHING WENT WRONG ERROR. The peculiar thing is that it didn't even get to the stage where it would send me a verification SMS (Facebook's 2-step verification feature), it just said something went wrong and that's it.
Somehow, just somehow, this feels like a hardware related thing. I don't know, but I think I am going to offer my colleague some money to swap our Nexus!