If you connect over localhost (127.0.0.1) you shouldn't experience that particular issue. I wouldn't muck much with the pg_hba.conf but instead I would adjust your connection string:
psql -U someuser -h 127.0.0.1 database
where someuser is your user you're connecting as and database is the database your user has permission to connect to.
Here is what I do on Debian to setup postgres:
http://www.postgresql.org/download/linux/debian/ (Wheezy 7.x)
as root …
root@www0:~# echo "deb http://apt.postgresql.org/pub/repos/apt/ wheezy-pgdg main" >> /etc/apt/sources.list
root@www0:~# wget --quiet -O - https://www.postgresql.org/media/keys/ACCC4CF8.asc | apt-key add -
root@www0:~# apt-get update
root@www0:~# apt-get install postgresql-9.4
root@www0:~# su - postgres
postgres@www0:~$ createuser --interactive -P someuser
Enter password for new role:
Enter it again:
Shall the new role be a superuser? (y/n) n
Shall the new role be allowed to create databases? (y/n) y
Shall the new role be allowed to create more new roles? (y/n) n
postgres@www0:~$ createdb -O someuser database
postgres@www0:~$ psql -U someuser -h 127.0.0.1 database
Enjoy!