"Host key verification failed" even with removed ~/.ssh/known_hosts

OK, answered.

When I run ssh with -v option, it showed me the actual error.

It was caused by mistakenly setting wrong access rights to /dev/tty, whatever that is, and ssh somehow didn't like it. sudo chmod 666 /dev/tty seemed to fix it.

So the poster's problem has been resolved. But in case others come to this question by searching and their symptoms are not coming from the same cause:

Deleting ~/.ssh/known_hosts (or just the offending line in it) will purge the cached host key. However, there is also a system-wide cache, which will be stored someplace like /etc/ssh/ssh_known_hosts. Host keys won't be cached there unless that's specifically requested. But if you're having host key verification issues, have a look in both of these files.