The approach I like for this kind of problem is to treat each string as a base-4 representation of a number. You just need a base-4 convertor (with this specific alphabet), and then your code is just an enumeration from 0 .. 4^L - 1.

Using Math::BaseCalc, here's a simple solution (untested):

use Math::BaseCalc;

$calc4 = new Math::BaseCalc(digits=>[qw/A T C G/]);

print($calc4->to_base($_), "\n") for 0 .. 4 ** $L - 1;
[download]

(You probably need to left-pad the string with 'A's to length L. Here 'A' maps to 0.)

Update: Good catch, ++jdalbec (fixed off-by-one bug).