Okay, I got a bit further but I think I've run into a limit in the framework.
Since Kernel is registered as a singleton in the bootstrapping process, I figured injecting a Kernel instance in ExampleProvider would make sure I could get the correct instance of Schedule.
Turns out this idea was partly correct: I can access the correctly registered instance of Schedule after I inject Kernel into ExampleProvider.
However, this only works within application context (if the application was started from public/index.php.
In an artisan context, two Kernel instances are created.
I'm not sure how or why, but https://github.com/laravel/lumen/blob/912befc/artisan#L31-L33 makes a new instance of Kernel (despite being declared as a singleton and another instance already existing).
This is the Kernel instance that's ultimately used when executing the schedule, so any changes to the schedule of the previously created Kernel are lost.
At this point, I'm not sure if there is another approach - I'm also not entirely sure if this is a bug or expected behaviour.
For now, I'll require my users to explicitly call my provider from their schedule, which will result in the schedule being set twice (and on the Kernel that will be used for execution).