Replacing in call app

1. Is it even possible for third-party app to replace the default in call app?

Yes, starting with API 23 it is possible.

2. Are there any sample implementations using this API out there I may use as a reference? I've found the google implementation, but this is a system app which makes use of some permissions that are not available for other apps (ex: android.permission.MODIFY_PHONE_STATE).

The only one I'm aware of, is the sample I created https://github.com/arekolek/simple-phone that was already mentioned in the other answer as well.

3. Am I correct in the assumption that after providing a correct InCallService manifest registration and a stub implementation I could expect to find my app under Default Apps -> Phone? Do I need to declare something else?

Actually, no.

Like mentioned in another answer on the topic, you don't need InCallService at all to appear on that list.

What you need though, is to register an activity with two intent filters, one with a tel Uri scheme, and one with an empty scheme (having just one of them is not enough):

<intent-filter>
    <action android:name="android.intent.action.DIAL" />
    <data android:scheme="tel" />
</intent-filter>
<intent-filter>
    <action android:name="android.intent.action.DIAL" />
</intent-filter>

It is vaguely mentioned in the docs, and stated explicitly in AOSP code.

That is enough to appear on that list. Only then, to provide the UI for the call, will you actually need the InCallService.