Do you mean a new story that you've never heard before? Or just any time you replay it? If you mean the first one, about 3 weeks because I always get the legendaries, but never use them. (Too OP) If you mean the second one, I beat Yellow a few days ago, and it only took me 5 days! (I think it would've been less, but I got a massive headache after Lavender Town)
I think you'll need at most 16 games. (Sorry, I don't know)
As for how long it will take you? I'm going to say at least three weeks per each game, at least, so no more than 48 weeks! (I think, I've never actually filled any pokedex)