pg_dump does not finish
I was able to figure out which file in the database storage was the culprit, by copying all the files to /dev/null.

cp -vR /usr/lib/postgresql/8.4 /dev/null


(The path to your DB files might differ)

The currupt file could not be copied, but there was nothing I could do to change that. (so it was most probably a FS error or hardware failure)

So I restarted the server with a forced fsck (e.g. touch /forcefsck), to make sure the FS would do the best to fix itself. This might not be the way you'll want to go, since it is possible to have a total data loss afterwards, but I was able to preserve the most precious data already beforehand, so I took the risk.

After reboot I could finally access the inaccessable table again, but I am not sure, if the data contained is corrupted or not. Anyway, I do have a backup now, which I can disect to find out, and my server can go back online for now...

I recommend reading the wiki of postgres about corruption and the slides of this FOSDEM presentation for some more info on DB corruption