This should do it -- not using any advanced algorithms, just a simple, two-pass distribution:

#!/usr/bin/perl
use strict;

use List::Util;


# -----[ Constants ]--------------------------------------------------
+----------

my  @ORGLTR = qw /a b c d e f g h i j/;
my  @REQNUM = qw /1 2 3 4/;
my  $LTRREP = 10;                       # Number of times we repeat ea
+ch letter


# -----[ Generate unrandomized list ]---------------------------------
+----------

my  @basgen = ();

foreach my $curltr (@ORGLTR)
{
    for (my $currep = 0; $currep < $LTRREP; $currep++)
    {
        push @basgen, $curltr;
    }
}
my $basdsp = join '', @basgen;


# -----[ Randomize ]--------------------------------------------------
+----------

my  @rndstr = &List::Util::shuffle(@basgen);


# -----[ Break it down ]----------------------------------------------
+----------

my  $ltrcnt = @ORGLTR;                  # How many distinct letters in
+ original set?
my  $numcnt = @REQNUM;                  # How many numbers in requeste
+d results?
my  $rescnt = @rndstr;                  # How many letters in full set
+?

my  $basdst = int($ltrcnt / $numcnt);   # Base integral distribution
my  $remltr = $ltrcnt % $numcnt;        # What isn't covered by the ba
+se
my  $supdst = $numcnt / $remltr;        # Supplemental distribution

if ($numcnt % $remltr)
{
    print "Sorry -- $LTRREP x $ltrcnt letters cannot be redistributed 
+equally as $numcnt numbers.\n";
}
else
{
    my @wrkltr = @ORGLTR;               # Letters to work on
    my $rndstr = join '', @rndstr;      # The randomized string

    print "Original String:  $rndstr\n";

    # Perform base distribution
    {
        foreach my $curdst (1 .. $basdst)
        {
            foreach my $curnum (@REQNUM)
            {
                my $curltr = shift @wrkltr;
                $rndstr =~ s/$curltr/$curnum/g;
            }
        }
    }

    # Perform supplemental distribution
    {
        my $curnum = 0;
        my $supcnt = $ltrcnt * $remltr;
        foreach my $curdst (1 .. $supcnt)
        {
            foreach my $curltr (@wrkltr)
            {
                $curnum++;
                if ($curnum > $numcnt)
                {
                    $curnum = 1;
                }
                $rndstr =~ s/$curltr/$curnum/;
            }
        }
    }

    # Display result
    print "   Final string:  $rndstr\n";
}


# -----[ Cleanup ]----------------------------------------------------
+----------


exit;

__END__


# -----[ Fini ]-------------------------------------------------------
+----------
[download]

Results:

D:\PerlMonks>remap-nodebug.pl
Original String:  ibcdhjfifhiabahgejedgihgacchdijaedgihcifjejfghecgdae
+cjdaibcgacaegjcbegghfeibbfdhhjbjbdadbacfdffbijfe
   Final string:  1234422324112143141433431334412114334312412234133411
+344132331311323213342112224444222414213242223421

D:\PerlMonks>
[download]

Update: Clarified reason for apology message.