The Butcher did not always show up. It just had a 2/3 chance of showing up. It’s easy to test for yourself, because you can restart the game and you only have to walk as far as the cathedral entrance to see if the quest appeared. It always appeared in multiplayer, but the quests are not randomized in multiplayer.

There are 16 quests in 6 groups, and 1 random quest from each of the first five groups is removed.