Unlike Date::Calc, Time::Local comes with perl. Untested:

use Time::Local "timelocal";
my ($month, $mday, $year) = split /-/, "01-23-2004";
my $wday = (localtime(timelocal(0, 0, 0, $mday, $month-1, $year-1900))
+)[6];
[download]

But if you are doing much date work, it's worthwhile to learn how to use Date::Calc or DateTime.

Update: adjusted year and month to be localtimey. Thanks isotope.