Try The Roadhouse (contact the venue directly) too. It's a great venue to play and usually has good sound and atmosphere, plus right in the Centre of town. They always ask for replacement bands or people who need shows, so should be able to help out.
Future Noise are cool, but don't put that many gigs on.
I helped put on a fair few rock gigs at The Walkabout in town too - and the manager is up for most things. I wouldn't recommend it for seriously heavy shit, but maybe worth a shot if you get desperate.
The Grand Central is the biggest rock venue in town and put on live band nights for free every week. They book up well in advance, but the sound guy/organiser is cool and well organised and could stick you on a bill with 3 other like-minded acts if you get in touch.
I know a few more, but give me a shout if you need further help!