Laravel pertenece a muchos donde no tiene uno de

Puede usar whereDoesntHave() de Eloquent restricción para obtener lo que necesita:

// get all Videos that don't belong to category 2 and 3
Video::whereDoesntHave('categories', function($query) {
  $query->whereIn('id', [2, 3]);
})->get();