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.