Labyrinth is probably the most luck based map in the game. Binlor is the standard answer, but the Berserker both has the hardest time gaining piety for him and stands a lot to lose for not keeping up.
I recommend a Human Berserker with Bearmace. A lot of people talk as if the Bearmace solves the map by itself, but it really doesn't. It's entirely possible to play through most of the map without getting a chance to break any walls that matter. I prefer Human to Orc here because you don't want a high starting damage. You want monsters to survive so you can get knockbacks. The best situation is if you can find a meatman and just push him all the way across the map, connecting all of those snarling corridors. You pretty much have to find either WEYTWUT, WONAFYT, or ENDISWAL.
Fun fact about WONAFYT. It will always try to place a monster in one of the squares directly north, east, south or west of you, only filling in diagonals when there is no other space. You can use this information to predict where summoned monsters will appear and position them so that they will let you knock down specific walls.
On the matter of the gods, it is definitely worth sending a Tinker to the Southern Swamp and scumming for Tikki Tooki. Once you have him, you will also be able to get Pactmaker, and then the number of altars that spawn will go from 2 or 3. That's a huge power boost, and it doesn't cost you anything.