As I see it, though, it's difficult to skip a test that requires unavailable modules.

Not really:

#!/usr/bin/perl

use strict;
use warnings 'FATAL' => 'all';

use Test::More;

BEGIN {

    if ( eval { require Cache::Memcached } ) {
        plan tests => 1;
    }
    else {
        plan skip_all => "Cache::Memcached is not installed";
    }

}

{

    require_ok( 'My::Module' ); # or whatever you want to test

}
[download]