3rd-party recovery images (TWRP, ClockworkMod, ...) offer an option to "format" or "wipe" (mkfs, really) the /data partition. This should be much closer to what you seem to be expecting from a "factory reset".
I know enough to do this, but obviously most people think a "factory reset" is sufficient. That is a problem - defaults matter.
[0] modulo further hidden state that I am not aware of or in touch with. For example my S4-i9500's emmc firmware which got corrupted somehow and bricked the device.
No? TWRP can flash images to any partition you like iirc. has an ADB sideload feature too... Or am I misunderstanding?