On some AVRs some timers share a prescaler. This prescaler can be stopped (set TSM, then PRSYNC). Then set the initial timer counter values of both timers with required offset. Enable both timers, set everything up. Then enable the prescaler and both timers start counting at the same time, staying in sync as they go.
Changing PWM duty cycle is easy. Changing frequency or the phase difference requires stopping of the prescaler. Still, with careful coding, it can be made almost invisible.