My cluster disappeared, but data is still there
Alright, I managed to solve it.

I tried to create the cluser

pg_createcluster 8.4 main


It complained that 8.4 was not an installed version. Alright then, this confirms my suspicion, that at some point postgres was upgraded to the latest version in the debian repos, and the data left behind.

So I went to reinstall 8.4 (Remember to backup your data dir, if you want to follow these steps. Don't hold me accountable for any dataloss)

sudo touch /etc/apt/sources.list.d/pgdg.list
sudo echo "deb http://apt.postgresql.org/pub/repos/apt/ wheezy-pgdg main" | sudo tee /etc/apt/sources.list.d/pgdg.list
wget --quiet -O - https://www.postgresql.org/media/keys/ACCC4CF8.asc | sudo apt-key add -
sudo apt-get update
sudo apt-get install postgresql-8.4
pg_lsclusters 


The output of pg_lsclusters showed that the 8.4 main cluster was created during the installation. I was afraid that it would have nuked the data dir with a fresh installation, but it didn't. Running psql revealed all the old data was still there