Between which phases is the sky moonless for at least 1/2 the night?

I would have to estimate that it would be between the lunar phases of Last Crescent and First Crescent. The Moon sets/rises within about 3 hours after the Sun, and this ought to give you a mostly moonless night.