Instead of returning subs which constantly evals strings (your eval $evalN lines), you can just eval a string that defines a sub once, something like this:

#!/usr/bin/perl -l

use strict;
use warnings;

my @subs = (
    q/ { my $i=0; sub { print "($i) First sub, sir!"; ++$i; } } /,
    q/ { my $i=0; sub { print "($i) Another sub, sir!"; ++$i; } } /
);

my @code = map { eval $_ } @subs;

$code[rand(2)]->() for (0 .. 20);
[download]

I hope that isn't too obscure. It just places two strings into an array. Each string is a block of code defining a variable and returning a sub using that variable. Later the strings are eval'ed in order to generate callable code. And last, the code is actually called. The random index is there just to make it clear that there is a closure in the game.

Sorry about that "sir!" thing, I saw Full Metal Jacket the other day and I can't get it out of my head. Be happy that my subs aren't mooing.