I solved this question on my own in Haskell at the time it was posted. It involved using a couple nested maps and some other things that were quite complicated to get my head around (as I remember). However, recently I've been experimenting with using lists as monads, and found my solution to this puzzle. Reworking it from that point of view, it becomes nice and clear. I know you're dabbling with Haskell, so I thought you might be interested.

import Char  -- for intToDigit

gen :: Int -> Int -> [String]
gen 0 _ = []
gen len max = do
  d  <- map intToDigit [0 .. max-1]
  ds <- [] : gen (len-1) max
  return (d:ds)
[download]

Below is the first version I came up with. You might not want to read it. It's rather ungainly.

gen :: Int -> Int -> [String]
gen 0 _ = []
gen len max =
  concat (
    map (
          \digit -> [digit] : (
                                map ( digit : )
                                    ( gen (len - 1) max )
                              )
        )
        ( map intToDigit [0 .. max-1] )
  )
[download]