イメージとしては、ps auxを叩いて同じ実行ファイルを探して、pid見て、その後の処理をするかどうか判定すればいいかなーって感じですかね。
で、ぐぐったら「Proc::ProcessTable」ってなモジュールがあったので、これ使ってみます。

use strict;
use warnings;
use utf8;

use Proc::ProcessTable;

my $p = Proc::ProcessTable->new();

# 起動した時のPID(自分自身のPID)
my $pid = $$;

# $p->tableで配列リファレンスが返るので、全部チェック。
for ( @{ $p->table } ) {
    # コマンドが「perl check.pl」+ pidが自分と違う -> 他のプロセスで実行中 -> 自身は終了
    die if ( $_->{'cmndline'} =~ /perl\scheck\.pl/ && $pid != $_->{'pid'} );
}

# 以下、重複したくない処理...

ま、ホントはジョブキュー(TheSchwartzとか、Gearman)とか使って、制御した方がいいんでしょうかね。
今回の要件は、
「crontabで起動するscriptがあって、前回の処理が終わってない場合は、処理しない」
だったので、これでいいか・・。