Can I write over the the previously printed-out array elements?

The easiest way is to turn off buffering and start each output with a carriage return character and end with sufficient trailing blanks:

$|=1; # flush output after each print
@outputs = qw/fred jim sheila barney/;
$maxlen = 6;
$delaysecs = 1;
for my $out (@outputs) {
   printf "\r%-${maxlen}s", $out;
   sleep($delaysecs);
}
print "\n";
[download]

If your sentences wrap onto the next line on the terminal, you'll have to do something more fancy.