That's what I proposed in one of my earlier messages. I have no idea if it works, but I guess it's worth to try it at least. But yeah, using 5 Exp. Shares and having the Smeargle (or whoever has the moveset) get the kills might just put it under 5. Don't quote me on it though, I've done it often enough to see my Pokemon at least grow to level 8 (without the above mentioned things). I guess one could go out of his way to RNG a gen 4 game where Staryu doesn't receive boosted Exp... xDYea, I think that wouldn't work. According to bulbapedia, KO'ing the Mimic/Rage user before the battle ends causes the glitch to fail. This will almost certainly level up the Staryu.
However, the glitch allows Ditto to learn Hydro Pump. I suppose breeding a Staryu with a Ditto would pass Hydro Pump if both Pokémon know the move?
(any gen 4 Staryu's wouldn't work either I believe, because it's only possible in gen 3 to begin with)