Try something along these lines:

#!/usr/bin/perl
use strict;
use warnings;

use Encode qw(from_to decode encode);

my $str = '...';

my $encoed_utf8 = from_to($str, 'UTF-8', 'ISO-8859-1');
my $decoded = decode('UTF-8', $str);
my $finally_utf8 = encode('UTF-8', $decoded);
print $finally_utf8, $/;
[download]

I have no idea if it actually works, but it's worth a try.

The language I'm using now (have to use it other than perl to do some things) has some nice functions for string character set encoding, but it seemed like i was getting nowhere

That doesn't surprise me. Encoding guessing relies on characteristics of human language to get it right (for example every UTF-8 file is also a valid Latin-1 file, but it usually doesn't make much sense for a human), so it is bound to fail if your data contains rubbish encoded into UTF-8.