An important update - if anyone hits this kind of a problem.

What's been going on on my system was the systemd restarted clamd service due to timeouts. This went on for some time until systemd gave up and failed the service. After some time most other services that depend on clamd failed permanently aswell (in effect if I got clamd working, other services still did not run).

There's a way to tell systemd to timeout after a specific amount of seconds.
I've added a line:
"TimeoutStartSec=600"
to the clamd.service unit file inside /usr/lib/systemd/system/clamd.service

Now the problem is solved for me.