Not so sure that player characters (Gold, Brendan, Lucas, etc) would've made good companions. Being trainers they would've shared similar goals and ambitions to Ash. I wouldn't want to see each gym leader having to be battled an extra time, they'd have made better rivals. I think they missed a trick them not appearing.
In Kanto, a character like Giselle, for example, could've made an interesting temporary companion. Maybe an extended period of travelling with Todd, perhaps Todd even obtaining some Pokemon? (he was destined to capture that Aerodactyl, and not just on film!) Duplica would've been good, if a bit one-dimensional (always dressing up as people).
In the Orange Islands, I would've liked to have seen Tracey given some more character development, especially in terms of his Pokemon. Also, that Water-type trainer Marina would've added another dimension to Misty, who by this point was slowly turning into a more boring mother figure. Both being Water-type trainers, they could've made good rivals.
Someone previously mentioned Sakura. Wanting to break away from her sisters, I believe she would've made an interesting companion. Falkner wanting to locate his father (Walker in the manga) might've made interesting viewing, and Bugsy is supposed to be some researcher, which could've also led to some interesting stories involving ancient/ legendary Pokemon.
In Hoenn, I agree that Wally should've been involved in some form, he was a good character in the games and the manga. Otherwise I think Ash, Brock, May and Max was a half-decent gang, though Max could've done with more development, as he never really appealed to me. Seeing more of Nicholai might've also been interesting. I know how nerds love cosplayers! During the Kanto Battle Frontier, maybe Pike Queen Lucy could've joined up and developed her interest in Brock a bit? (Might've even made a good exit storyline for him). Not really sure there was much to add from the Sinnoh gang. Perhaps some of the 'stat trainers' from the games could've had more extended appearances? Everyone loves Riley! Quite liked the idea of Nando's struggle between being a trainer and a coordinator, would've liked to have seen more of that. Lyra and Khoury could've made good character if they had done a Johto Battle Frontier arc, but they didn't... Not watched enough of BW to comment, but from what I have read Cilan and Iris haven't impressed me all that much, but theres enough characters who pop up now and then to get over that.