Actually, i think that using an array of array references is a wonderful fit for this problem. You just need to familiarize yourself with how Perl dereferences them:

my $two_d = [
   [1,2,3],
   [4,5,6],
   [7,8,9],
];

# how many columns?
print scalar @$two_d;

# how many rows in second column?
print scalar @{ $two_d->[1] };
[download]

use Math::Matrix;
use Data::Dumper;

my $two_d = [
   [1,2,3],
   [4,5,6],
   [7,8,9],
];

my $m = Math::Matrix->new($two_d);
print Dumper $m;
[download]

L-LL-L--L-LL-L--L-LL-L--
-R--R-RR-R--R-RR-R--R-RR
B--B--B--B--B--B--B--B--
H---H---H---H---H---H---
(the triplet paradiddle with high-hat)

Set up the outside array as your columns and the inside array as your rows. Now, creating a new column is simple and adding an entry to an existing column is still easy. Maybe something along the lines of:

sub new
{
    my $class = shift;
    my ($max_rows) = @_;

    my $self = bless {
        max_rows => $max_rows,
        data => [],
    }, $class;
}

sub add_column
{
    my $self = shift;
    push @{$self->{data}}, [];
}

sub add_value
{
    my $self = shift;
    my ($x, $y, $value) = @_;

    return unless $x <= $max_rows;
    return unless $x >= 0;

    $self->{data}[$y][$x] = $value;
}

sub get_value
{
    my $self = shift;
    my ($x, $y) = @_;

    return $self->{data}[$y][$x];
}
[download]

Maybe you want an array(ref) of hash refs so you can use the hash key as the column name? Probably not as memory efficient as an AoA depending on empty columns.

my $ary = [
    { c1 => 1, c3 => 3 },
    { c2 => 2, c3 => 3, c4 => 4 },
    { c5 => 5 },
];

my @cols = qw( c1 c2 c3 c4 c5 );

# to set a vaulue in a col that may or may not exist....
$ary->[0]->{c2} = 2;

# print out as a table
print join "  ", @cols, "\n";
for my $ref( @$ary) {
    print join "   ", (map{ defined $ref->{$_}? $ref->{$_} : '~' }@col
+s), "\n";
}

__DATA__
c1  c2  c3  c4  c5  
1   2   3   ~   ~   
~   2   3   4   ~   
~   ~   ~   ~   5
[download]