I like using the GD module, and from what I hear it's much faster than Image::Magick.

What I might do to implement this:
read up the image file
GD.pm
create a matrix of the pixels and color intensities
Build a sub that returns the intensity based on the rgb.
define some characters that would work as shades of gray intesities
trial and error, perhaps analysing a single font of characters assigning a value based on positive coverage in a fixed area (fixed width fonts only)
this would be worked out ahead of time and set into a file or array for the generation of the final product
match neighbour colors inside a certain range as one color re-formatting the matrix
Build a sub to do that, run the foreach loops for x and y of the image like thus (x = 2; x < size; x = x + 3) if a 3x3 sample size was desired
another thing might be to look into the available modules and see if they support resizing, then do that first (or you could always require that the input file be sized already)
print out the html file based on the matrix.
Lots 'o print statements. I'd probably be printing to standard out during the x and y iterations of the pixels, converting each pixel and printing one line at a time.

Hope it helps.