Well at that point you might be better off asking yourself if it's perhaps worth making it actually 3D instead. 3D doesn't have to mean bad performance. If you don't use the effects and features that have a heavy cost. Probably better to use fixed-function transforms rather than shaders for the rotation I would think.
edit: or if you are really adamant about keeping it 2D why not use animated spritesheets? You could just have the rotation animation be pre-rendered. That would be significantly more performant I'd expect.