One problem you might run into is that you can't reliably get this list of users via a database query only since access (or editing) rights can be modified in code by any module. This means that a views based solution probably won't cut it either.
One possibility is to get a shortlist via a view / EntityFieldQuery / db_select(), and then loop through and check if each user has edit access using node_access(). For performance your query could limit to certain roles if you have large numbers of users without edit permissions.
Once you have you have your shortlist (I'm using an array of user objects here but adjust this code if you're working with a different format) do something like this:
$node = node_load(12345);
$accounts_with_edit_access = array();
foreach($shortlist as $delta => $account) {
if (node_access("update", $node, $account) === TRUE) {
$accounts_with_edit_access[] = $account;
}
}