Assuming tab seperated data this will do the job.

use strict;

while (<DATA>) {
    my @data = split(/\t/);
    my $city_data;
    my ($city, $state, $zip);
    do {
        $city_data = pop(@data);
    } while($city_data =~ /^\s*$/);

    if (($city, $state, $zip) = ($city_data =~ m/^(.*)\s+([A-Z][A-Z])\
+s+([0-9-]+)/)) {
        print "$city, $state $zip\n";
    } else {
        die "Could not parse $city_data\n";
    }

    my $x = 1;
    for my $line (@data) {
        print $x, " $line\n";
        $x++;
    }
    printf("%d %s, %s %s\n", $x, $city, $state, $zip);
    print "\n";
}

__DATA__
BIGGLE EQUITY MGMT ASSOC.       PIGGLE BIGGLING PLAN    FUTURES I & II
+  TWO LONDDDD CENTER      TRENTON NJ 97302-5115
AGRICULTURAL LIFE INSURANCE CO  MAIN    111 ELEVEN AVE PO BOX 123     
+  MORRISTOWN NJ 97631-0633
MILLENA BANC    MILLINER BANK & TRUST CO        456 THAUMATURGE AVENUE
+  NEWSOME MA 07145-6316
BRICKABRACK ADVISORS    LIBERTARIAN BANK        888 CRAZED CREEK ROAD 
+STE 11    MEMPHIS KY 77882-5394
FOO COMMUNITY BANCORP   THE FOOVILLE SAVINGS BANK       18 FOOL AVENUE
+  FOO NY 10567-1735
ELROND ASSET MANAGEMENT         BRA3255 CSHYTFD         ATTN SETTLEMEN
+TS DEPT.  466 LURCHING AVENUE     NEW YORK NY 10347
CRIPPLE CREEK INVESTMENT ADVISORS       GLIB TALKER     666 9TH AVENUE
+ 8TH FLOOR        NEW YORK NY 10235-2302
SEPARATIST STATE BANK   ATTN: JOSE KWAN         XYZ FINANCIAL CENTER  
+  145 TALKING FAST ROAD   NEWBURGH NY 07083-2340
[download]

Depending on the number of records there are you might think of verifying the addresses (using HTML::Form) at http://zip4.usps.com/zip4/welcome.jsp