my Ubuntu's graphics output had broken, and I had to reinstall it. To keep my data and settings, I just reinstalled it from a CD over the old system.
Everything went smooth, apart from the fact that I get errors on every update:

stan@stan-ThinkPad-T530:/var/lib/dpkg/info$ sudo apt-get autoremove
Reading package lists... Done
Building dependency tree       
Reading state information... Done
0 to upgrade, 0 to newly install, 0 to remove and 0 not to upgrade.
1 not fully installed or removed.
After this operation, 0 B of additional disk space will be used.
Setting up fontconfig (2.11.1-0ubuntu6) ...
Regenerating fonts cache... failed.
See /var/log/fontconfig.log for more information.
dpkg: error processing package fontconfig (--configure):
 subprocess installed post-installation script returned error exit status 1
Errors were encountered while processing:
 fontconfig
E: Sub-process /usr/bin/dpkg returned an error code (1)

There are two (possibly linked?) issues that are bothering me:

1. 1 not fully installed or removed. in the 6th line. It does not tell me which package is not fully installed or removed, and I have no clue how to find it out.

2. The error caused by fontconfig in the last line. I am getting this error after each update, since fontconfig is run each time.

cat /var/log/fontconfig.log gives me the following:

/usr/share/fonts: caching, new cache contents: 0 fonts, 4 dirs

... a lot of lines with various fonts ...

/usr/share/fonts/type1/gsfonts: caching, new cache contents: 35 fonts, 0 dirs
/usr/share/fonts/type1/mathml: caching, new cache contents: 1 fonts, 0 dirs
/usr/local/share/fonts: caching, new cache contents: 0 fonts, 0 dirs
/.local/share/fonts: skipping, no such directory
Re-scanning /usr/share/fonts: fc-cache: symbol lookup error: fc-cache: undefined symbol: FcDirCacheRescan

I've already spent so much time looking for a possible solution, and tried the following commands which were suggested here and there, among others

sudo dpkg --configure -a
sudo apt-get clean
sudo apt-get dist-upgrade

but all in vain. Any debugging help would be highly appreciated!

EDIT:

Shutupshare suggested doing apt-get install --reinstall libfontconfig1 libfontconfig1-dev libfontconfig1-dbg, this gives the following:

stan@stan-ThinkPad-T530:~$ sudo apt-get install --reinstall libfontconfig1 
libfontconfig1-dev libfontconfig1-dbg
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Reinstallation of libfontconfig1 is not possible, it cannot be downloaded.
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies.
 libfontconfig1-dbg : Depends: libfontconfig1 (= 2.11.0-0ubuntu4) but 2.11.0-0ubuntu4.1 is to be installed
 libfontconfig1-dev : Depends: libfontconfig1 (= 2.11.0-0ubuntu4) but 2.11.0-0ubuntu4.1 is to be installed
                          Depends: libfreetype6-dev (>= 2.1.7) but it is not going to be installed
E: Unable to correct problems, you have held broken packages.

EDIT2:

Output of dpkg --get-selections:

1) hold (gives nothing)

stan@stan-ThinkPad-T530:~$ sudo dpkg --get-selections | grep hold

2) purge

stan@stan-ThinkPad-T530:~$ sudo dpkg --get-selections|grep purge
rsyslog                     purge

3) deinstall

stan@stan-ThinkPad-T530:~$ sudo dpkg --get-selections|grep deinstall
libcap2:i386                    deinstall
libcgmanager0:i386              deinstall
libepoxy0                   deinstall
libffi6:i386                    deinstall
libglib2.0-0:i386               deinstall
libllvm3.5:amd64                deinstall
libpython2.7-minimal:i386           deinstall
libsystemd-daemon0:i386             deinstall
libudev1:i386                   deinstall

The rest has the status installed.