This is the simple solution I've implemented, following Tanktalus's advice:

my $stop;
my $speed = 0;
my $start = time;
while (<CONNS>) {
        $counter++;
        if ($counter =~ /00$/) {
                $stop = time;
                my $diff = $stop - $start;
                my $tdiff = ($diff == 0) ? 1 : $diff;

                $speed = sprintf("%.f", ($counter/$tdiff));
        }
        ... line processing ...
        print "Processed: $counter (at $speed lines/s)  \r";
}
[download]

Not so elegant or fast, but works. Thanks everyone!