That's one of my favorites! First, you will need to speak Barbarian. You can learn the lingo by visiting the spell shop in the barbi home village and buying the language primer.
Once you have that down, talk to the Barbi on the bridge and he will send you out on a "clean up the neighborhood" mission. Skellies, giants, centaurs, even sirens... he will ask you to kill all kinds of stuff!
Complete 3 of these tasks and you can open the gates any time you like. BTW - if he gives you a task for a mob you don't wanna kill, just delete it and ask him again. It won't affect the quest.