I just encountered this monstrocity in Chapter 4, but have no idea how to defeat it. It seems to be immune to all the attack types (pepper grinder, teapot, vorpal blade and the wooden horse). I am stuck!
There's no way to win against the Executioner - just evade his attacks for a time, and Alice will eventually get the chance to retreat. He's going to continue chasing you, so plan to continue evading his attacks and fleeing from him when you encounter him again.
The Alice Wikia notes:
Eventually you'll be able to defeat him, but I don't want to spoil his demise :)