The idea to use gmtime/timegm is a good one. Another simple idea is to go from noon of the source day. There is no daylight offset that will ever give you trouble if you go from noon.
perl -e 'use Time::Local qw(timelocal); print "".localtime(timelocal(0
+,0,12,23,1,2006)+86400*124)."\n"'
# prints Tue Jun 27 13:00:00 2006
Of course this all assumes that you aren't worried about the hours - but there are easy ways to handle those also. You just retain the hours,mins,secs from before the day conversion and replace the hours,mins,secs of the converted date.
my @a=qw(random brilliant braindead); print $a[rand(@a)];