How to run a background task in android when the app is killed

Question

I am very new to Android app development paradigm. To teach myself, I am trying to build an app which shows a notification when user receives a call. So far I have been able to do this using BroadcastReceiver

public void onReceive(Context context, Intent intent) {
    String state = intent.getStringExtra(TelephonyManager.EXTRA_STATE);
    String incomingNumber = intent.getStringExtra(TelephonyManager.EXTRA_INCOMING_NUMBER);
    //show notification
}

I have not shown the entire code here, since I am coding in Flutter, I have created a Event Channel that sends this information back to flutter code. But this works fine.

The main issue is that the aforementioned idea works, as long as my app is running. Unlike Truecaller, which shows a notification even if the app is not running. My question is how to do this.

I have searched on internet and found that Service is the way to go. However the official documentation cites the following limitations

Services running in the background can consume device resources, potentially resulting in a worse user experience. To mitigate this problem, the system applies a number of limitations on services.

While an app is in the foreground, it can create and run both foreground and background services freely. When an app goes into the background, it has a window of several minutes in which it is still allowed to create and use services. At the end of that window, the app is considered to be idle. At this time, the system stops the app's background services, just as if the app had called the services' Service.stopSelf() methods.

That is clearly not the intended use case that I am looking for. My particular use case is the following

1. User gets a call and my app is not running.
2. Some background thing (let's not call it Service, in order to avoid confusion) is running which detects the call event and gets the number.
3. It sends this information back to flutter, via event channel. (The app is still not running).
4. It shows a overlay notification (like Truecaller), in flutter.

Can someone please give me some pointers as to how this is done in general. Some example code (or link to some tutorial, or at least tell me how Truecaller is doing that) would be nice. Thanks in advance.

Most apps these days does this. So this should be very common. Unfortunately I am unable to find the exact thing I need to do in order to achieve this.

Note :

1. Facebook app also sends push notifications whenever a message is received, but I think that is different.
2. This question may be useful.
3. This also looks useful.
4. This article refers to the article in point 3.
5. Finally, Telephony plugin also uses similar ideas to get SMS in background.