Yet another way, though I totally agree that a much better solution would be to use an inherently sortable format for the hash keys from the start.

use strict;
use warnings;
use feature 'say';

my %data = ( 
             Apr14 => 2,
             Mar14 => 2,
             May14 => 2,
             Dec13 => 2,
           );  

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

say "key - $_ and value - $data{$_}" for 
            map      { s/ (\d{2}) (\d{2}) /$num_to_month{$2}$1/rx } 
            sort map { s/ (\w{3}) (\d{2}) /$2$month_to_num{$1}/rx }
            keys %data;
[download]