# I'm sure you have a very different (more sensible) way of
# mapping table values to their proper legacy encodings, but 
# this is just to show how to handle the data:

my %column_enc_map = ( columnA => 'cp1250',
                       columnB => 'cp1251',
                       # or whatever... );

for my $field ( keys %column_enc_map )
{
    # replace the hash values from the database with utf8 strings:

    $database{$field} = decode( $column_enc_map{$field}, $database{$field} );
}

# %database values are now in utf8; you can load them back to the database via updates