You can catch Magnemite and Koffing in the Virbank Complex. Be sure to catch some before you go to Roxie's Gym.
The Virbank Gym is in the southeast area of the city, with a neon sign on top.
Inside the gym, talk to Clyde if you haven't already. He gives you a Fresh Water, and if you talk to him again, he gives you some advice about Poison-type pokémon.
Go up through the door behind Clyde. This club is also Roxie's gym. P-O-K-E-M-O-N! Pokémon!
The guy at the bottom left operates the audio, but he doesn't challenge you to a battle.
If you try to talk to Roxie, she can't hear you because of the loud music, so you have to defeat her drummer and guitarist first.
The drummer is Roughneck Nicky. He has a level 14 Grimer and a level 14 Koffing.
The guitarist is Guitarist Billy Jo. She has a level 14 Venipede and a level 14 Koffing.
After you defeat the drummer and guitarist, you can talk to Roxie to challenge her. She has a level 16 Koffing and a level 18 Whirlipede.
When you win, you get the Toxic Badge. Roxie also gives you TM09 Venoshock.
As you step off the stage, a blonde guy walks up to you and asks you to go to Pokéstar Studios. Roxie leaves to go convince her father to return to his job as ship captain.