^Purrloin is horrible, the gyms hate it and you don't even get a bunch of Munna trainers to grind against early-game any more. I know it sounds harsh but seriously there are hundreds of better options
Anyway, I just finished another run using a team of Volc/Mag/Lucario/Krok/Weezing/Starmie. Out of all these only Koffing and Staryu haven't been tiered yet so I can give some feedback on them:
Koffing: It's always great when something you expect to be shitty turns out to be a really useful team-mate. Koffing starts decently because of its huge Defence stat (although it doesn't really accomplish anything that Magnemite doesn't) but really starts to prove its worth in Castelia. It takes out nearly everything in the sewers and destroys Burgh's Gym almost singlehandedly, though relying on Sludge is annoying and again, Magnemite does a lot of stuff better. It's weird since you wouldn't expect Koffing and Magnemite to have similar roles, but due to Magnemite's amazing typing it acts a lot like Koffing when everything's using Normal, Bug and Dark attacks. It's around Clay that Koffing really begins to shine, though. Immunity to Excadrill's hugely powerful Bulldoze and the Defence to tank everything else it has is very welcome, though it can't do all that much back in fairness and you'll need a few potions to actually win with Koffing (or Weezing). The Fighting, Poison and Ground resistances come into play very very often against vanilla trainers, Koffing really makes you remember just how good Poison-typing can be defensively. You also have the ability to attack decently from both sides of the spectrum, as your STABs are all special but can be backed up well by attacks like Return, Fire Blast, Assurance and Payback. Koffing does struggle against Elesa, Skyla and Marlon and you'll find that Weezing takes a lot more damage than you might think from remotely powerful Special STABs, but its utility against normal trainers as well as its dominance against certain bosses (namely Ghetsis who now uses a stupid physical Hydreigon) help separate it from the Poison-type crowd. A very good Mid tier Pokemon.
Staryu: Another surprise, I adore this thing. You can immediately evolve it into Starmie, which annihilates every normal trainer in the vicinity with its blazing 115 Speed and powerful dual STABs, since you pick up the Psychic TM straight after you get access to Staryu. Starmie's 100 Special Attack is sufficient with such reliable STABs, and Psychic is a much better attack than it was in previous generations due to BW2 Unova's plethora of Poison and Fighting-types. After hitting up all the trainers on Routes 14 & 13 you can pick up Blizzard and Thunder in Lacunosa Town, which help Starmie's coverage tremendously. 70 acc isn't detrimental because nearly everything you'll use Thunder on won't be able to deal significant damage to Starmie anyway, and the same can be said for Blizzard aside from Grass-types and a couple of dragons in Gym 7. Plasma grunts give you problems with Scrafty and sometimes Drapion, but aside from that Starmie beats everything they have. I mentioned Starmie's bulk being worse than Oshawott and Jellicent's and whilst that's true, I found it with just the right stats to survive very strong attacks with a sliver of HP and quickly finish off the foe next turn thanks to its Speed. Starmie curbstomps the Dragon Gym with Blizzard (when your opponent's Haxorus has Dragon Tail for STAB you can afford to miss loads, don't fret) and Marlon's Gym gets destroyed through a mixture of Psychic, Thunder and Starmie's typing. With a final moveset of Surf/Psychic/Thunderbolt/Ice Beam Starmie hits 15 of the 22 Pokemon in the league for SE damage, a coverage feat which is hard to match when one considers that all 6 of Iris' Pokemon get hit for double damage and none of them outspeed or have an easy time killing Starmie (Lapras' Tbolt 2HKOs but so does yours). IMHO Starmie is one of the best Water-types in the game since it's very very quick, has great coverage almost straight away and sweeps at least 4 bosses, 6 if you can kill Ghetsis' Drapion and limit Caitlin's Shadow Balls. It's hampered by availability mostly, if it were available before Clay I'd try to make a case for top but as it is Starmie fits into the High tier nicely. I think one could make a case for Mid if there were enough examples of Starmie's bulk letting it down, but I don't think there'll be too many. Other things that keep Starmie out of the Top Tier for me are its poor performance against Colress and Grimsley, and an initial grind that might be necessary when you catch Staryu.