Yup. The only caveat is that you'd be using Timer1 to generate the PWM (since timer0 is used for millis). But the Timer1 on the Tiny85 is not the same as the Timer1 on most of the AVR product line (it's an 8-bit high speed timer that can be clocked off the PLL and has more prescaler options, instead of the usual 16-bit timer) - it's not any more complicated to use, it's just that it's not quite the same, so there's less code available online to steal. On the plus side, it's a wonderful timer!
I2C or SPI works - with SPI you'd be running short on pins. There's no hardware serial - you can get serial, but it's a software implementation - so it's half-duplex, and send/receive are blocking.