We show that the nu = 8 integer quantum Hall state can support Majorana zero modes at domain walls between its two different stable chiral edge phases without superconductivity. This is due to the existence of an edge phase that does not support gapless fermionic excitations; all gapless excitations are bosonic in this edge phase. Majorana fermion zero modes occur at a domain wall between this edge phase and the more conventional one that does support gapless fermions. Remarkably, due to the chirality of the system, the topological degeneracy of these zero modes has exponential protection, as a function of the relevant length scales, in spite of the presence of gapless excitations, including gapless fermions. These results are compatible with charge conservation, but do not require it. We discuss generalizations to other integer and fractional quantum Hall states, and classify possible mechanisms for appearance of Majorana zero modes at domain walls.