Launch systemd service before login prompt

After being able to change the hostname on the fly, I am trying to run a systemd service before the login prompt, as the first time It asks for login credentials, the value printed on the screen refers to the previous content (previous startup) of /etc/hostname.

I already tried what is suggested here, but It didn't work for me

EDIT: It has some dependencies with other services as well, so launching the hostname-changing service as one of the first ones (i.e. DefaultDependencies=false) is not an option