ATtiny: no support for multiplication?
The ATtiny does not have a hardware multiplier, but software multiplication is not quite as expensive as you imply. See the AVR200 application note and associated code for some optimized multiplication and division routines.

Sine and cosine calculations can be accelerated using lookup tables, effectively trading memory space for processor cycles. However, as @DaveTweed correctly pointed out, algorithmically approximating sine and cosine in software will push the cycle count up nearer the range you fear.