Please leave +1 if this works for you! :)
The goal is to win by fatigue. You want to use your removals (and your Nerubians) to keep the board clear, there should be plenty if you are efficient with them. Don't worry about doing damage to his face, as fatigue will take care of it all.
Try to use your Coldlihight Oracle when you can bounce it back with Youthful Brewmaster. Best if you can make his hand size go beyond 10 cards. e.g. through multiple oracles, and/or with Naturalize, etc.
There should be plenty of healing to keep you at a safe level vs his buffed charging / windfury Dunemaul Shaman.
Majordomo was just for the lol. To be more efficient it's been subbed out for Tree of Life.
It's a fun deck to play against Highlord Omokk. Check out the videos posted by flohmannjr and Windslot.