Solution

What you need is a Class, which you can use to update page title [or some other stuff], but it should not be injectable.

You can define a plain JS Class Not as @injectable. You can then use the APP_INITIALIZER to instantiate the class manually. The instance thus created will not be accessible using DI, but can be saved and shared by using global/static variable.

Here is the sample stackblitz. I have only logged to console, you can update as needed.

TitleService Class that updates title using updateTitle method.
PageTitleService Class that will subscribe to router and calls TitleService.updateTitle.
pageTitleServiceInit factory function to manually instantiate PageTitleService.

Code

import { APP_INITIALIZER, Injectable, NgModule } from "@angular/core";
import { BrowserModule } from "@angular/platform-browser";
import { FormsModule } from "@angular/forms";

import { AppComponent } from "./app.component";
import { HelloComponent } from "./hello/hello.component";
import {
  ActivatedRoute,
  NavigationEnd,
  Router,
  RouterModule
} from "@angular/router";
import { RandomComponent } from "./random/random.component";
import { filter } from "rxjs/operators";

// ================ TitleService ======================
@Injectable()
export class TitleService {
  updateTitle(title: string) {
    console.log("new title: ", title);
  }
}

// ================ Initalizer Factory ======================
function pageTitleServiceInit(router, route, titleService) {
  return () => {
    new PageTitleService(router, route, titleService);
  };
}

// ================ PageTitleService ======================
export class PageTitleService {
  constructor(
    router: Router,
    activatedRoute: ActivatedRoute,
    titleService: TitleService
  ) {
    router.events
      .pipe(filter(event => event instanceof NavigationEnd))
      .subscribe((x: any) => {
        console.log(activatedRoute);
        titleService.updateTitle(x.url);
      });
  }
}

@NgModule({
  imports: [
    BrowserModule,
    FormsModule,
    RouterModule.forRoot([
      { path: "random", component: RandomComponent },
      { path: "hello", component: HelloComponent }
    ])
  ],
  declarations: [AppComponent, HelloComponent, RandomComponent],
  bootstrap: [AppComponent],
  providers: [
    TitleService,
    {
      provide: APP_INITIALIZER,
      useFactory: pageTitleServiceInit,
      deps: [Router, ActivatedRoute, TitleService],
      multi: true
    }
  ]
})
export class AppModule {}

Just an observation why injecting in a component (App component) would not be such a bad idea:

1. Showing title in the browser window is a Application requirement and app component is actually the container (or root) your application.
2. So can't we say that it is a concern of application (app component) to have the title updated promptly?
3. A service as i understand can be seen as a helper and App component can use this service to update the title
4. You can have a init method in the service which will be called from app component so that it can start listening to router event and update the title. This makes it very imperative, explicit too and you can move calling this init method to some other component if required.

Solution

Instead of injecting the service via your app.component.ts, you could inject the service via the app.module.ts (or via your app-load.module.ts)

Eg:

@NgModule({
  ...
})
export class AppModule {
  constructor(pageTitleService: PageTitleService) {}
}

Use APP_INITIALIZER or APP_BOOTSTRAP_LISTENER. More details you can find here.

For use Router in APP_INITIALIZER set initialNavigation option to true. Or use APP_BOOTSTRAP_LISTENER (but you skip first navigation in this case)

for add initalizer you need add provider for it

{
  provide: APP_INITIALIZER,
  useFactory: (router) => yourFunction,
  multi: true,
  deps: [Router]
}

I think there are a few options possible.

1. Simply create an instance yourself. An service is noting more than a regular class. You can create an instance yourself new PageTitleService(router, activatedRoute, pageService) However, this requires you to pass an instance of the objects defined in the constructor.
2. Use the injector. You can call injector.get(PageTitleService) to get an instance. Unfortunately injector is also a service which should be inejcted in an component or service.

In your case, you are going to need dependency injection. You could try option 1 and also manually create instances of router and activatedRoute, but they might have their own dependencies. And their dependencies might also have dependencies.

You could create a regular Singleton which has some kind of init function that does al the initial work. Something like this:

class Singleton
{
  private constructor()
  {
    console.log("hello");
  }

  private hasStarted = false;

  private static _singelton :Singleton
  static get(): Singleton{
    return Singleton._singleton || (Singleton._singleton = new Singleton())
  }

  pubic init(router: Router, activatedRoute: ActivatedRoute, titleService: Title): void{
    if(!hasStarted){
      //do whatever you want
      hasStarted = true;
    }
  }
}

In your appcomponent:

constructor(router: Router, activatedRoute: ActivatedRoute, titleService: Title){
  Singelton.getInstance().init(router: Router, activatedRoute: ActivatedRoute, titleService: Title);
}

This way there will only be one instance of your singleton an everyting in the init will only be executed once.

Note: nothing is realy private in typescipt. Something like this is still possible.

const singleton = Singelton.getInstance();
singelton['hasStarted'] = false;
singleton.init(...);

Is it possible for you to create a title.ts in your root folder and do:

export const titleConfig = {
  title: '',
}

and access that object from whenever you need it, and change it in your router

import { titleConfig } from 'src/app/title';
// ...more magic goes here

export class PageTitleService {

  constructor(
    private router: Router,
    private activatedRoute: ActivatedRoute,
    private titleService: Title
  ) {
    this.router.events
      .filter((event) => event instanceof NavigationEnd)
      .map(() => this.activatedRoute)
      .map((route) => {
        while (route.firstChild) {
          route = route.firstChild;
        }

        return route;
      })
      .filter((route) => route.outlet === 'primary')
      .mergeMap((route) => route.data)
      .subscribe((routeData) => titleConfig.title = routeData['title']); // change here
  }

}

if you are using ChangeDetectionStrategy.Onpush then you can do a { ...routerData['title'] } or add a setTitle method to the object. I'm not sure.