Вам не нужно определять AoA в конструкторе - просто самый верхний arrayref. Что касается благословенного хэша, AoA - это просто ссылка на массив.
Ваш конструктор идеален.
Чтобы вставить, вы делаете 2 вещи:
# Make sure the row exists as an arrayref:
$self->{AoA}->[$row] ||= []; # initialize to empty array reference if not there.
# Add to existing row:
push @{ $self->{AoA}->[$row] }, $stuff;
Или, если вы добавляете элемент известного индекса, просто
$self->{AoA}->[$row]->[$column] = $stuff;
Ваша проблема с выполнением push @{$self->{AoA}}[$row]
состояла в том, что вы разыменовали уровень массива 1 слишком рано.