It's clear that purely random mutations don't work in the sense that an infinite number of monkeys won't produce Shakespeare even if you kill of the monkeys that fail.

The monkeys would write Shakespeare if you tested their output character by character instead of waiting till the end. That's how evolution works too - in tiny cumulative achievable steps.