usa un frame para mostrar los check y despues pasale un parametro para ver si esta marcado o no. Osea.
<script>
marcar=false
function marcarlos(){
if(marcar==false)
marcar=true
else
marcar=false
document.getElementById("marcar").src="checks.php? marcar="+marcar
}
</script>
<input type=button onclick="marcarlos()" value="marcar/desmarcar">
<iframe src="checks.php?marcar=false" id="marcar"></iframe>
Y en la pagina checks.php pones
Código PHP:
if($_GET["marcar"]==false)
{
/*
todos
los
checkbox
sin
marcar
*/
}
else
{
/*
todos
los
checkbox
marcados
*/
}