systemd-journald Doesn't start at all
After renaming the hostname, deleting & recreating /etc/machine-id
by running systemd-machine-id-setup
and rebooting to apply these, systemd-journald came back to life!
Try deleting /var/log/journal
in case that there are any remainders from previous restoring attempts. Then set Storage=persistent
in /etc/systemd/journald.conf
and reboot.
Normally systemd should recreate /var/log/journal
during reboot.
If this doesn't help try
mkdir -p /var/log/journal
systemd-tmpfiles --create --prefix /var/log/journal