It's true, that dying man giving the butcher quest will simply sometimes not be outside the entrance to the cathedral. I was surprised too.

Were you playing multiplayer? Multiplayer always starts with Butcher and Skeleton King.