Garrick Stout in Dernholm is the Melee Master. It is possible to become both melee and dodge master, you just have to play your cards right.
The expert is the war veteran at Blackroot. He's North of the mayor's palace, and South of the docks. The guy you want to talk to is the only one wearing a different outfit in the little camp.
You can find the co-ordinates of Blackroot on T-A and just walk there... but it'll probably be more fun if you follow the quest... Did you do the Ghost quest (the one in the mine) in Shrouded Hills? That quest will lead you to Dernholm (ask people in SH for directions). Another quest in Dernholm will lead you to Blackroot.
No. Go to the castle in Dernholm, start talking with the wuss of a king Praetor and offer your services to the kingdom. He will send you to Black Root to pick up back taxes and mark your map. OR you could by a train ticket in either Tarant or Ashbury to Black Root. On a side note, if you get the quest from Praetor and have reasonable persuasion, you can convince Dante, a NPC in the bar there, to help you regain the taxes so he will regain his favor with Praetor. If you succeed in getting him to come along, you will be happy to know he is counted as a quest follower and doesn't count against your max followers. The guy you are looker for is Heckemer Ogg (spelling?), labeled a grizzled war veteran, on the patch of land west of the mayors house. Talk nice to him and he will agree to train you to expert in Dodge/Melee and tell you where to find the masters of each. Also, you can get expert Melee training from the pit master on the Isle of Despair before scheduling any fights.