Sure. I don't know what your task primary key is, so I'll just make one up that I'll call taskid. If its composite, this can still be done, but you'll need to pass both to the value (typically done easiest with serialization).
print '<form method="post" action="">';
$toq= mysql_query("SELECT * FROM tasks WHERE done=0");
while ($row = mysql_fetch_assoc($toq))
printf('<label for="%d"><span class="labelsystem">%s</span><span class="labelregion">%s</span><span class="labeldescription">%s</span></label>' . PHP_EOL, $row['taskid'], $row['system'], $row['region'], $row['description']);
printf('<input id="%d" type="checkbox" name="todo" value="%d" />' . PHP_EOL, $row['taskid'], $row['taskid']);
Which should give you similar to what you have in the first screenshot. You can use CSS for the markup of that instead; I removed the - from them as I don't like them. You should be able to use the CSS pseudo classes :before and :after to add them if you want (won't work with IE < 6.0 of course).
Then when you process them, you simply retrieve from the todo array:
if (isset($_POST['todo']) && is_array($_POST['todo']))
// This is where we write validation and verification. I just assume a flat integer
$bResult = false;
$int = (int)$in;
if ((string)$int == $in)
$bResult = true;
$aTodo = array_filter($_POST['todo'], 'isIntString');
// here we would handle SQL if it needs to be escaped (integers do not).
$sQry = 'UPDATE tasks SET done = 1 WHERE taskid IN (' . implode(', ', $aTodo) . ')';
// and go from here to update