SSH without Password

In order to ssh from Host1 to Host2 without password, the following needs to be done:

user1@Host1:~> ssh-keygen -t rsa
Generating public/private rsa key pair.
Enter file in which to save the key (/home/user1/.ssh/id_rsa):
Created directory '/home/user1/.ssh'.
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in /home/user1/.ssh/id_rsa.
Your public key has been saved in /home/user1/.ssh/id_rsa.pub.

If ~/.ssh doesn't exist on Host2 as user2, create one:

user2@Host2:~> mkdir -p .ssh
user2@Host2:~> chmod 700 .ssh

Append user1's public key to authorized_keys and authorized_keys2 in user2@Host2:.ssh/:

user1@Host1:~> cat .ssh/id_rsa.pub | ssh user2@Host2 'cat >> .ssh/authorized_keys'
user1@Host1:~> cat .ssh/id_rsa.pub | ssh user2@Host2 'cat >> .ssh/authorized_keys2'

user2@Host2:~> chmod 640 .ssh

Now ssh from user1@Host1 to user2@Host2 should be possible without password:
user1@Host1:~> ssh user2@Host2\

Avoid Host Verification

ssh -o "StrictHostKeyChecking no" user@host

Debugging

Set LogLevel to DEBUG in /etc/ssh/sshd_config
/etc/init.d/sshd restart
Then try to ssh, debug messages will be logged to /var/log/secure
PS: Once you have resolved the issue remember to switch back LogLevel to INFO and again restart sshd.