I remember that Snooker added Dooku to Qui-Gon’s funeral. That could get you started.
The next best place to integrate Dooku might be at the Jedi Council.

The problem is introducing him as an important character. In these scenes, he would merely be a random background character with a vague connection to Qui-Gon.

It would be great to have a scene of Dooku talking to anyone. You could use the footage of the balcony scene at the temple and create a new one that features Qui-Gon talking to Dooku. In this setting they can talk while standing next to one another and gazing off into the distance, that should make it a lot easier to composite everything.

The only question is what they should talk about.