All you need to do is keep a global count of each combination, right?

my %total_count;
foreach $site1 (@site1) {
   my @site1_parts = split(//, $site1);

   my %counts;

   foreach $site2 (@site2) {
      my @site2_parts = split(//, $site2);

      for my $i (0..$#site1_parts) {
        $counts{$site1_parts[$i].$site2_parts[$i]}++;
        $total_count{$site1_parts[$i].$site2_parts[$i]}++;
      }
   }

   push(@count_collection, \%counts);
}

foreach my $counts (@count_collection) {
  foreach (sort keys %$counts) {
    print($_, ': ', "$counts->{$_}/$total_count{$_}", $/);
  }
   print($/);
}
[download]