An alternative, lazy approach would be to use Date::Manip. It makes formatting a little easier:

use Date::Manip;

sub fakedate {
    my ($lower_bound, $upper_bound) = @_;
    my $timestamp =  $lower_bound + int (rand $upper_bound - $lower_bo
+und +1);
    return UnixDate( "epoch $timestamp", "%d-%m-%Y %H:%M:%S" );
}
[download]

Update: okay, I just learned another thing: Date::Manip is slow. Very ;-) I used Benchmark to compare arturo's fakedate with mine:

Benchmark: timing 1000 iterations of fakedate_a, fakedate_mk...
fakedate_a:  0 wallclock secs ( 0.03 usr +  0.00 sys =  0.03 CPU) @ 33333.33/s (n=1000)
            (warning: too few iterations for a reliable count)
fakedate_mk: 13 wallclock secs (12.76 usr +  0.09 sys = 12.85 CPU) @ 77.82/s (n=1000)

Thanks to arturo and OeufMayo for pointing this.

-marcink