I am just posting this for anyone who is feeling lost and hopeless as I did when I found this question. It seems that sometimes by editing some psotgresql-related config files, one can accidentally change the permissions of the file:

Note how pg_hba.conf belongs to root, and users cannot even read it. This causes postgres to not be able to open this file and therefore not be able to start the server, throwing the error seen in the original question.

By running

sudo chmod +r pg_hba.conf

I was able to make this file once again accessible to the postgres user and then after running

sudo service postgresql start

Was able to get the server running again.