Use strings instead of arrays. The following shows that a 100 element array containing strings of 4 million characters takes less that 400MB which is well within the capabilities of most modern machines.

It also shows a subroutine for doing the substitutions that very closely mirror the syntax you have above. And finally, it shows making 300,000 random substitutions takes less than 1 second on my machine:

use Devel::Size qw[ total_size ];;

$a[$_] = '*'x4e6 for 0 .. 99;;

print total_size \@a;;
400003052

sub change { 
    my( $y, $x, $text ) = @_; 
    substr $a[$y], $x, length $text, $text;
};;

print time(); 
change( int( rand 100 ), int( rand 4e6 ), 'test' ) for 1 .. 3e5; 
print time;;
1219523963
1219523963
[download]