How fast can I cycle an AC SSR?

There is no harm in turning on or off a zero-crossing SSR at every zero crossing.

I did exactly that once in a system that had to control 24 heaters simultaneously. The control algorithm produced a 0-255 value proportional to how much each heater was supposed to be driven. The low levels used a Bresenham algorithm to decide each half-cycle whether each heater should be on for the next hal-cycle. It worked very well.

No worries switching on and off at 120 Hz, but as you mentioned you are hard limited to a pulse width of 1/120 Hz. If you are running directly from a wall switch, you are ok using 1/2-cycle as your minimum pulse width, but if running through a transformer, use an even number of half cycles to prevent having a DC bias.

Pulse width modulation is a natural here since your pulse rate is always going to be a multiple of 120. In a heating application, a 8-bit PWM with feedback turning "on" once per 2.13 (256/120) seconds and "off" on a 120- or 60-second boundary should be good if the load resistance is appropriate.

I agree with @JackCreasey there is nothing in the datasheet that says zero crossing.

You could get aliasing, depending on your frequency. The SCRs will stay on for the remainder of the half-cycle regardless of when you trigger them.

I suggest going with about a 2 second cycle minimum, especially if you don't want to synchronize to the mains zero crossings, a bit more would be better. Unless you have a really, really good reason that's plenty fast enough for thermal setups. Often 10-20 seconds is more than good enough (except for things like IR heaters which change temperature significantly in seconds).

About a 2-3 second cycle is worst-case for causing thermal fatigue on the power semiconductors. We saw a multi-million dollar screwup some years back caused by the die bonds fatiguing causing overheating and failure (in the on-state typically) of the power semiconductors. Modern ones are better, and it helps to keep well away from the maximum rating.