You have some file that has ownereship such that root can not access the file via permissions.
You need to turn on full auditing to get the path of the offending file.
Execute
auditctl -w /etc/shadow -p w
And see if you can generate the error again. Then you should get a path with the next avc message.
As far as I know, for this to work I would need to have auditd running, isn't that the case? As I pointed in my initial post, auditd cannot start!
OK, I can force permissive mode, then start auditd, switch back to enforced mode and then execute auditctl. Then, may be, I could find the offending path/files causing the issues with the other programs I have listed in my logs, but how do I deal with the auditd itself? auditctl requires auditd to be running in order to show the paths, isn't that not the case?