What you want is a cartesian product of 2..9, and then a cartesian product of each of the letters allowed for each of the numbers. I've been out of the perl game for a while but I can comment on how I'd do it in python. The following will print 81 combinations of letters (3*3*3*3) for each possible four digit group of numbers.

# digit_letters is defined as in the original
def go():
  import probstat # module for combinatorics
  valid_numbers = range(2,10) # 2..9 inclusive
  for (number_set) in probstat.Cartesian([valid_numbers]*4):
    answers = []
    letter_sets = probstat.Cartesian([digit_letters[number] for number
+ in number_set])
    for (letter_set) in letter_sets:
      answers.append(''.join(letter_set)) # combine the four letters
    print number_set, ", ".join(answers)
[download]

I tried to break it down into shorter lines than I normally use, but all it is doing in pseudo code is

for (four_numbers) in Carteisian([2..9]*[2..9]*[2..9]*[2..9]):
  print four_numbers
  for (four_letters) in Cartesian(the letters for four_numbers):
    print four_letters
[download]