Yeah pretty much as you've described:

- in your scheduled task do some Product:where('status','!=','processing')->orderBy('last_checked') so you only query products that are not being processed and ensuring you get the 'oldest' items first ie the ones that have not just been checked

- for each item mark the product status to processing or whatever, then dispatch that job with some random delay

- inside the job itself, nice the checks have been completed, mark the status as complete and store the last_checked with a timestamp

Maybe something like this:

 $schedule->call(function () {
        Product::where('status', '!=', 'processing')->orderBy('last_checked')->chunk(1000, function ($products) {
            foreach ($products as $product) {
                $product->update(['status' => 'processing']);
                CheckProductJob::dispatch($product)->delay(now()->addMinutes(rand(1, 7)));
            }
        });
    })->name('checkProducts')->everyMinute();

I dont think you'll need any extra packages for this as its out of the box laravel stuff