I was having the same problem and just managed to fix it now.
Since the file bitcoin.conf does not exist inside ~/.bitcoin, Just create one.
Here's what did:
Enter letter 'a' (to edit the file). Then type:
Press the ESC key, and press ZZ to exit vi
Apparently the password that bitcoind started with is (for one reason or the other) different from the one you are trying. (i also have a feeling that bitcoind misbehaves like that because no password was defined; since there was no bitcoin.conf)
Now, even though you have changed the password, it will NOT be effective until bitcoind has been re-started. But since it won't even accept the stop command (./bitcoin-cli stop) due to the authentication issue;
You will need to kill the process, and restart bitcoind. It will work fine afterwards:
pkill -9 -f bitcoind
Hope this is helpful