Well, if you want to keep your 'print HTML as one print statement' paradigm, you just Build the content of the table outside of the print statement:

#!/usr/local/bin/perl -w

use strict;
use CGI;

my %host=( 'camel', 'flea', 'frog', 'green');
cgiout();

sub cgiout {
  my $q= new CGI;
  my $tablecontent=[$q->th(['key', 'value'])];
  for (sort keys %host) {
    push @$tablecontent,  $q->td([ $_, $host{$_} ]) ;
  }
  print $q->table( { border => 1, -width => '100%'},
                   $q->Tr( $tablecontent),
                 );
}
[download]

This results in this table:

key	value
camel	flea
frog	green

Update: Removed slightly snide comment open for misinterpretation.

CU
Robartes-