If you know that the form was submitted then you could take the absence of a value as proof that it was unchecked.
But yes, there is a simple solution that lets you keep checkboxes: use hidden inputs.
<input type="hidden" name="checkbox" value="off">
<input type="checkbox" name="checkbox" value="on">
When checked, the checkbox's "on" overwrites the hidden input's "off".