Well, I wasn't actually able to catch it, so I realize this doesn't totally count. Regardless, wanted to share the story. In RSE, you get to choose your starter when you find the professor from that generation being attacked by a Poochyena. I was soft-resetting my Ruby version one day in an attempt to get a shiny Mudkip. Instead, in that first battle, the damn Poochyena turned out to be a shiny! In case you don't know, you have no way to catch it in that first battle, so there was nothing I could do. (>_<)
But getting back to what this thread is really about, I think the earliest was a random shiny Shuppet encounter in my UM version. It was in that abandoned or haunted house where you typically find Mimikyu and some others, and I think I was just level grinding when I randomly found and caught it. I think this was about midway through the actual game.