In U.S. sports lingo, a deep bench can actually refer to a couple of different things.
In some sports (such as basketball), a team tends to start the same five players game in and game out (barring injury or other disqualification of a starter). In those sports, the role of the "bench" players is to come in as substitutes when the starters get tired or run into foul trouble, or (occasionally) to match up with a certain player on the opposing team—either to neutralize him or to exploit an unusual weakness he has. Having a deep bench in basketball thus generally means having substitute players who are sufficiently skilled that the team's quality of play doesn't fall off dramatically at any position when substitutes come in to replace the starters.
In other sports (such as baseball) the "bench" is set up less to serve as a kind of backup unit to the starters—as in basketball—and more to carry an array of players with specialized skills appropriate to specific strategic situations in a game. For example, a baseball team may carry (in addition to an array of left- and right-handed relief pitchers with specific in-game roles, whose competence at their jobs determines whether the the bullpen is deep [strong] or shallow [weak]) several position players to serve as left- or right-handed pinch-hitting specialists; one or two exceptionally good glove man to come in in the late innings of close games when their team has the lead, to strengthen the infield or outfield defense; an exceptionally fast runner to pinch-run for a slower player in a critical situation; a player with excellent bat-control or bunting skills to move runners over in the late innings of a close game; and a backup catcher to handle defensive duties when the regular catcher gets pulled from the game for a pinch hitter or pinch runner. Beyond those substitute roles, a team may use a platoon system at one or more positions, whereby one player starts against right-handed pitchers and another player starts against left-handed pitchers.
Consequently, in baseball, having a strong bench doesn't mean merely having reasonably competent reserves to replace the starters when the starters must come out of the game. It means having players who can step in and capably perform the various crucial roles that may arise in the course of a game; and conversely, having a weak bench means having a roster of players on which no one can perform certain special tasks well—no one who can enter the game and effectively lay down a bunt, steal a base, replace a powerful but slow left-fielder in the ninth inning and run down a ball hit into the gap, etc.
In the jokey example sentence, “a deep bench of brutal madmen” suggests a "deep bench" in the basketball sense of the term, where the idea is that you can take one player out and put a substitute in and not experience any drop-off in team performance. The irony here, of course, is that the performance that doesn't drop off consists of brutality toward the nation's citizens (and others who run afoul of the government) and wayward (if not insane) policy decisions. Kim Jong-il replaces Kim Il Sung, and things continue as usual; then Kim Jong-un comes in for Kim Jong-il, and again the North Korean government doesn't miss a beat (or a beating).