I didn't manage to change the bootloader (and also skipped the kernel), but I have found a pretty usable workaround.
I now make a screenshot on shutdown and use this screenshot in an init.d script. It now takes about 15 seconds before the screenshot shows up, not what I was looking for, but still a substantial upgrade from the >1 minute it usually takes to boot.
Interestingly, the real boot time also seems to decrease by about 12 seconds.
There's only one possibly large downside: the screenshot (>1 MB) is written to the internal memory everytime the DR shuts down, possibly reducing the lifetime of the device.