This reads $j lines, then skips until $m is reached, then starts reading again. Prints to STDOUT, not to a new file. But that isn't your main concern, is it? ;^).

#!/usr/bin/perl

use warnings;
use strict;

my $m = 3;  ## lines in each set
my $j = 2;  ## lines that should get printed

my $i = 0;
while (<DATA>) {
        $i++;
        print;

        ## skip
        if ($i == $j) {
                <DATA> while $i++ != $m;
                $i = 0;
        }
}

__DATA__
foo 1 2 3
foo 2 3 4
foo 4 5 6
bar a b c
bar b c d
bar c d e
baz q w e
baz w e r
baz e r t
[download]

Update: Oops, missed the "random" bit. Let's try this:

#!/usr/bin/perl

use warnings;
use strict;
use List::Util qw/shuffle/;

my $m = 3;
my $j = 2;

MAIN: while (1) {
        my @set;

        for (my $i = 0; $i < $m ; $i++) {
                last MAIN unless defined ($_ = <DATA>);
                push @set, $_;
        }
        for ((shuffle @set)[0..$j-1]) {
                print;
        }
}

__DATA__
foo 1 2 3
foo 2 3 4
foo 4 5 6
bar a b c
bar b c d
bar c d e
baz q w e
baz w e r
baz e r t
[download]