If you don't call random() from any other part of your code, it should be safe.
However, you probably should just set a flag in the interrupt handler, and pick that flag up in the main() function, and do all your random stuff there, including preparing the next random number.
Also, you can easily generate your own random number genrator using a linear congruential generator, which will be good enough for the use you're suggesting (in fact, a simple table of size 256 might be good enough!)
If your problem is flicker, though, then that won't get better with randomness IMO. You're probably better off just settling on a N:M quantization of on/off distribution. A random distribution might make the noise you may hear from certain fixtures less static, though, and thus maybe make it slightly less unpleasant. It's better to have no noise, though :-)
Here's a function I would use to figure out whether the next is "on" or "off":
char curVal;
char ratioN; // N >= 0, N <= M
char ratioM; // M > 0, M <= 127
bool getOn() {
curVal += N;
if (curVal >= 0) {
curVal -= M;
return true;
}
return false;
}
Also, you probably don't need 100 steps of control -- try 20-30 steps of control for a pretty smoothly varying system, especially if you're driving things like incandescent lights.