You could try something like this:

#! perl -slw
use strict;
use Data::Dump qw[ pp ];

sub gen {
    my $href = shift;
    my @kByV = sort{ $href->{ $b } <=> $href->{ $a } } keys %$href;
    my @dist = ( $kByV[0] ) x $href->{ $kByV[0] };
    shift @kByV;
    while( @kByV ) {
        my $k = shift @kByV;
        my $v = $href->{ $k };
        my $n = int( @dist / ( $v+1 ) );
        my $p = $n * $v;
        splice( @dist, $p, 0, $k ), $p -= $n for reverse 1 .. $v;
    }
    return \@dist;
}

pp gen( { A => 4, B => 2, C => 3, D => 1 } );
pp gen( { A => 5, B => 4, C => 3, D => 2, E => 1 } );
[download]

Outputs:

C:\test>1030688.pl
["A", "C", "B", "A", "D", "C", "B", "A", "C", "A"]
["A", "B", "C", "A", "D", "B", "C", "E", "A", "B", "D", "C", "A", "B",
+ "A"]
[download]