2 Years have passed. Nothing says that the leaders can't change their Pokemon and start over. Also, consider that foreign Pokemon are now scattered all over the region.
True. I just think that it would be a little weird for Clay to go from having an Excadrill to having a Drilbur/other weak Pokemon. I suppose they could just change it to suit their new position, but I wouldn't really like it if they made some of them "weaker", as it were.
I wonder if Shizui will have a Gyrados.. I just noticed his pants look a lot like them. Since he's probably the second gym leader his Gyrados probably wouldn't know much so it wouldn't be that hard especially if they give us Mareep or Blitzle early on.
He seems like a Dewott person to me. Design of the leader doesn't have much to do with the Pokemon they use though, except in glaringly obvious cases like Homika.
Where's it saying she uses a Koffing in the anime?
Here.
Yeah, there actually is a picture of a Koffing behind her, but that doesn't mean she has to use one.
Well the anime all but confirms that she will use it. They want to promote the games, and their not going to do that by giving her a random Koffing.
And still, where does it say also she'll be the first Gym leader?
It doesn't, but she only has two Pokemon and she's one of the first to be revealed, so it's all but confirmed.