Ok, here's my current solution at 192 chars.

sub a{$#_?(sort{length$a<=>length$b}map{my$s=$_;my@l=grep{$s ne $_}@_;
+map{my$t=$_;my@m=grep{$t ne $_}@l;a(i($s,$t),@m)}@l}@_)[0]:pop}
sub i{($_,$t)=@_;chop$t while!s/\Q$t\E$/$_[1]/&&''ne$t;$_;}

print a qw(logger gerbil log analog);
print "\n";
print a qw(GATTACA ATTACA GATT AAGAT CCC);
[download]

update1: trimmed another 4 chars from the i sub, and stopped clobbering globals:

sub i{my($s,$t)=@_;chop$t while$s!~s/\Q$t\E$/$_[1]/;$s}
[download]

... if we're clobbering $_, we can trim another 5:

sub i{($_,$t)=@_;chop$t while!s/\Q$t\E$/$_[1]/;$_}
[download]

update2: 163 chars, strict and global-clean, all in one sub, named assemble (or 156 if it's named a):

sub assemble{$#_?(sort{length$a<=>length$b}map{my$s=$_;my@l=grep$s ne$
+_,@_;map{my($t,$u)=($s,$_);my@m=grep$u ne$_,@l;chop$u while$t!~s/\Q$u
+\E$/$_/;assemble($t,@m)}@l}@_)[0]:pop}
[download]

   MeowChow                                   
               s aamecha.s a..a\u$&owag.print