The approach I've taken (with WWW::Mechanize::Chrome, WWW::Mechanize::Firefox and Archive::SevenZip) is two-fold:

1. Allow to override the program used from an environment variable. This gives easy outside configuration to override any location that my program logic uses. I've put that logic into the main module instead of Makefile.PL, since I expect that the override might be useful not only when testing the module but also after the module is installed. For example when testing a new version of Chrome against an existing module, you might want to override the executable name from the outside.
2. Each test file individually skips if the binary is not found. This is some ugly boilerplate that I prepend to each test file to guard against the binary not being there at all. I'm not aware of a good way of skipping test files with a N/A marker, so the tests still "pass" even if nothing was tested at all.

I do this in a couple of ways. In one, my WiringPi::API, I fail hard during the initial build phase. This instructs the testers to ignore everything all together very early (ie. skip this distribution immediately as to not waste cycles). This method, however, will also prevent a user from installing the software if the required libraries aren't installed***.

use warnings;
use strict;
 
use ExtUtils::MakeMaker;
use version;
 
my $min_wpi_ver = 2.36;
 
if (! -f '/usr/include/wiringPi.h' && ! -f '/usr/local/include/wiringP
+i.h'){
    print "wiringPi is not installed, exiting...\n";
    exit;
}
 
if (my $path = (grep { -x "$_/gpio" } split /:/, $ENV{PATH})[0]){
    my $bin = "$path/gpio";
    my $gpio_info = `$bin -v`;
 
    if (my ($version) = $gpio_info =~ /version:\s+(\d+\.\d+)/){
 
        my $installed_ver = version->parse($version);
 
        if ($installed_ver < $min_wpi_ver){
            print "\nyou must have wiringPi version $min_wpi_ver" .
                  " or greater installed to continue.\n\n" .
                  "You have version $version\n";
            exit;
        }
    }
}
else {
    print "\ncan not determine wiringPi version. Ensure version ${min_
+wpi_ver}+ " .
          " is installed. Can't continue\n";
    exit;
}
...
[download]

In other distributions, I may allow the install to happen, but only run specific tests (and/or test files). My RPi::WiringPi does this. The entire test suite is designed around a literal hardware test platform I've built myself, that I run tests on 24x7 locally, in a CI environment:

use warnings;
use strict;
 
use lib 't/';
 
use RPiTest qw(check_pin_status);
use RPi::WiringPi;
use RPi::Const qw(:all);
use Test::More;
 
if (! $ENV{RPI_SHIFTREG}){
    plan skip_all => "RPI_SHIFTREG environment variable not set\n";
}
 
if (! $ENV{RPI_MCP3008}){
    plan skip_all => "RPI_MCP3008 environment variable not set\n";
}
 
if (! $ENV{PI_BOARD}){
    $ENV{NO_BOARD} = 1;
    plan skip_all => "Not on a Pi board\n";
}
[download]

In essence, if you have tests you want the testers to run, but only some of the tests require the underlying library/whatever, skip the files/specific tests you don't want them to see. Otherwise, bail out in your build regimen, so the tester servers don't need to waste time fetching and installing all prereqs, just to find there are no tests to perform at all.

Note that in the latter case above, I'm checking environment variables that need to be not available before I skip. You can cobble any manner of conditions to make this choice. Also, I don't have an example here on skipping individual or bunches of tests within a file, I'm just skipping the whole file itself. Read up on the docs from your testing documentation (I assume it's the same as mine, Test::More or similar) to sort how to include some tests within a file, but skip others.

***: Double-edged sword with exiting from the Makefile. Some people want the software installed regardless of whether the back-end library is available or not. In some software I've written, I permit this, and just skip all tests in all files. In this case, and most, I just barf immediately, as I feel if someone doesn't understand what the software is for, they don't want it installed anyhow. Those that might, they can fetch and hack the makefile.

This method, however, will also prevent a user from installing the software if the required libraries aren't installed

Or if the required libraries are installed in some place other than /usr/include.
Maybe that doesn't happen with wiringPi, but it's happened to me wrt other modules - and there's nothing that angers me more (wrt perl) than having to rewrite a Makefile.PL because of unrealistic author expectations regarding the location of the requisite library, or of the way in which it is being made available to the compilation.
If wiringPi.h does not get found during the compilation, then the cpantester report will record an "UNKNOWN" result, and little (if anything) would have been gained by detecting the missing dependency at the Makefile.PL step anyway.

It's at the compilation phase that the library files need to be found.
The Makefile.PL doesn't need the library. IMO it should just write the Makefile according to the EU::MM directives, and if the user hasn't made the required library available to the compilation, then (s)he will soon find out.

(Mind you, I'm perhaps a bit more "touchy" about this than most.)

Cheers,
Rob