Shininess in GSC is determined by IVs/DVs. Therefore, you will get a shiny every time the game generates the right combination of IVs. The odds of this happening are about 1/8192, I believe, so with enough attempts, odds are that you'll get a shiny starter.
The limitation on gender stems from the fact that both gender and shininess are based on IVs. In gen II (to assign a gender to Pokemon sent over from gen I), Pokemon in the lower portion of the IV spread for attack are female, while those higher up are male (so males are physically "stronger" attack-wise than females). The cutoff for this is determined by the Pokemon's gender ratio. Since starters are 1/8 female (1 female: 7 males), and IVs in gen II range from 0-15, the bottom eighth of the attack IVs (0 and 1) are the female IVs, and the others are male IVs. Shiny Pokemon can't have an attack IV of 0 or 1, so female starters cannot be shiny.
My starter on Red (Blastoise) showed up as shiny when viewed by a gen II game. That meant that it had a particular set of IVs (10s for a lot of them, and some variability in the others), which made it compatible with gen II's shininess component.