From the documentation of Foreach Loops: "... the foreach loop index variable is an implicit alias for each item in the list that you're looping over." Meaning you can simply assign back to the $Date_Ref variable in order to assign to the element in the array. You can even modify the original variables by writing for my $Date_Ref ($Map_Request_Date, ...) { ... (Update: It seems choroba has made the same point while I was typing.)

In the following, I've taken the liberty of writing the code the way I might have (see also Use strict and warnings), although I prefer using modules like DateTime (plus DateTime::Format::Strptime) for all my date/time handling needs, even if it seems like overkill sometimes. (Update: Note that I kept your technique of adding a leading zero to $Day instead of switching to sprintf because I wanted to demonstrate using if as a statement modifier, but if I were writing this from scratch I'd have used sprintf instead.)

use warnings;
use strict;
use Data::Dumper;

my %Months = ( 'Jan' => '01',  'Feb' => '02',  'Mar' => '03', 'Apr' =>
+ '04', 
    'May' => '05',  'Jun' => '06',  'Jul' => '07', 'Aug' => '08',
    'Sep' => '09',  'Oct' => '10',  'Nov' => '11', 'Dec' => '12'  );

my ($Date1,$Date2) = ('Jul  3 2016 10:45 UTC','Aug 12 2017 11:56 EST')
+;

my @Variables = ($Date1,$Date2);
for my $Date_Ref (@Variables) {
    my ($Month,$Day,$Year,$Time) = split ' ', $Date_Ref, 4;
    $Day = "0$Day" if length($Day) == 1;
    $Date_Ref = $Year."-".$Months{$Month}."-".$Day;
}

print Dumper \@Variables;

__END__

$VAR1 = [
          '2016-07-03',
          '2017-08-12'
        ];
[download]

Note: split ' ', ..., as opposed to split / /, ... has a special behavior, see split: "any leading whitespace in EXPR is removed before splitting occurs, and the PATTERN is instead treated as if it were /\s+/; in particular, this means that any contiguous whitespace (not just a single space character) is used as a separator.".