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:
vi ~/.bitcoin/bitcoin.conf
Enter letter 'a' (to edit the file). Then type:
rpcpassword=any_long_random_password
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
then
./bitcoind -daemon
Hope this is helpful