Excellent work Minstrel. Wouldn't it be cool to give him an indication of hair? You probably want to keep him bald, right, but I am thinking hair stubs. Indication of hair pores, you know, like the shaolin monks rather than the polished bald head of say Kojak. Does that make any sense? =)
I think it would make him look well hard, although the shaved head works well with the big brute image as well.

He does have a heroic look to him, maybe it's his steadfast, determined gaze into eternity so maybe you're taking him in a completely different direction?