This is kind of interesting to me, so I'm going to spend a little time researching it. I don't think you need to worry about the "few odd spreads" at all. The 252/252 spreads are the worst case, so if you can prove those are possible you're done. It shouldn't be too hard... Just gotta look at the various low level pokemon available in each game and see what EVs they give. There are guides on gamefaqs that show locations/levels.I do not know, this was brought up on #littlecup earlier today and... Without Power Items (and without Serebii's easily searchable encounter level thing which only exists for the 4th gen) it is a lot harder to be totally sure. I can check specific spreads without massive difficulty, and prove that they are possible, but its hard to be totally sure that a spread is impossible because I may have missed a Pokemon to train against that is hidden away somewhere (it seems the best Pokemon to EV train HP against is Lv. 5 Mirage Island Wynaut >_>).
I would not be surprised if a few odd spreads were indeed impossible in the 3rd Gen, but the vast majority should be. Not sure of the best way to handle this when ADV LC becomes a played metagame, having something like the illegal IV spread checker for EV spreads.. I think in this case it would be absolutely horrible to program, and only affect things in a tiny minority of cases.
For what it's worth, it looks like there are level 3 Caterpie in the Viridian forest in FR/LG, so getting to Mirage Island shouldn't be necessary for HP EV training. :)