I solved it by using vanilla JavaScript:
<input type="hidden" name="checkboxName" value="0"><input type="checkbox" onclick="this.previousSibling.value=1-this.previousSibling.value">
Be careful not to have any spaces or linebreaks between this two input elements!
You can use this.previousSibling.previousSibling
to get "upper" elements.
With PHP you can check the named hidden field for 0 (not set) or 1 (set).