Virgin have been crewing -800s with 4 crew for years! When I was at QF, they'd often do it if someone called in sick.
NZ regs allow an -800 to be operated by 4 cabin crew in normal circumstances & by 3 crew in the case of illness away from a crew base. Oz doesn't. This is because NZ requires 1 F/A for every 50 pax & Oz requires 1 F/A for every 36 pax.