Some of Microchip's enhanced midrange MCUs have a ZCD module that can synchronise the PWM timer to the mains zero crossing + up to eight PWM modules that could handle the TRIAC control in hardware + the facility to cascade timers via a CLC module to allow a high core clock speed while matching the PWM timebase closely to the mains half-cycle period. All that lot is 'set & forget' - i.e. the hardware will keep on producing the TRIAC firing pulses at the selected firing angles without intervention from the main program.
Its then just a matter of writing code to update the duty cycle registers from serial input, though due to the cost of isolating I2C, I'd select logic level serial with RS232 framing or SPI, to be able to use cheap common optoisolators.
I don't know if there are any Atmega chips that have comparable hardware synchronisation to an external signal for their PWM modules. That's something you should look into, however if it is possible you will have to leave the Arduino playground and read the real datasheets to write your own synchronous PWM driver.
You can also do it in software given some timer support, but it gets really gnarly if you need a multi-channel implementation especially when two or more channels must switch in a very short time interval but not simultaneously (i.e. phase angles differing by one step).