Once you progress through the main story missions far enough too gain the poison ability this is very simple and easy. All you need to do is highlight a red mission tab on the map and find one marked "feast." Travel to the mission area and simply poison the grog bowls in the area the orcs are hanging out in (on your mini-map, they'll have exploding icons at their locations in the camp, just in case you can't see them right away). Then just wait. Once the captain drinks, it only takes a few seconds before he dies. Even after they notice that the grog is poisoned, they still kept drinking it in my game.
P.s. I was spotted and killed a few in open combat and then climbed a ruined building until they stopped looking for me. Even after that, once the captain calmed down he started drinking again and died shortly after. Trophy popped immediately after his face hit the ground.