After messing up a little with apt-get, no matter what I did, I was getting this:
dpkg: warning: 'ldconfig' not found in PATH or not executable.
It was not a matter of PATH, because I tried to find ldconfig and it was missing indeed.
Here is how I fixed it:
aptitude download libc-bin
dpkg-deb -x libc-bin* libc_unpacked
cp libc_unpacked/sbin/ldconfig* /sbin/
And then everything was back to normal.