Beginner - 30x9 LED board

I am trying to build a 30x9 LED board which would be able to scroll inputted messages as well as have a couple basic animations saved in memory.

I have my LED board soldered together using the trick described in this video here: DIY LED Array Text Display Marquee - YouTube

This still takes up a ton of I/O pins, leaving little else - which is fine but if there is some trick around this, that would be cool.

Anyway, I am having 2 problems with this setup:
1) I have to turn off all rows except the one that I am blinking with each iteration but I can't find a way to actually do this programatically. The only thing I can find is to turn all rows to input mode "input" and then turn the current blink row to "output" mode - otherwise things get screwy. This actually works but it seams to be quite slow since you can visibly see the LEDs blinking (sort of a seizure mode). Is there a way around this?

2) I wrote the original program to support a smaller LED array and it worked just fine. After I scaled it up, my program quickly ran out of memory. My program was using the String class which I have read is a real memory hog but I was wondering if there were any already written programs for such a project. Or should I just convert the String(s) to char(s) and rewrite everything that way?
Lastly, is there any type of hardware the could aid me in such a project or is just a standard Arduino with jumper wires and LEDs all I need?

Got a schematic of things are wired up now?
Ideally could be like this: Arduino driving anodes connected in parallel across the 9 rows, with 4 TPIC6B595 shift registers used to sink current from the 30 columns.
Multiplex it by writing the anodes, sinking a column.
Write the anode, sink the next column.
Repeat across the display.
Hold each column for ~1mS for ~30Hz refresh rate.

The message to be displayed can be stored to & read from EEPROM, easy to make it quite long.

The way it is wired up is really quite simple (see attachment)

My knowledge of anodes and shift registers is nill - any easy tutorials on these?

Edit: Also, is there a way to limit the number of I/O pins used (currently at 24) somehow?

Untitled.jpg

Sure, use daisy chained shift registers - 3 pins to control the 30 columns and 9 rows.

Great. I have been able to find a local store that has those specific shift registers but I don't know anything about anodes and all I can find when searching is switches / dials that are anodized.

Is there a specific product number for an anode that would work for this and if so, how many anodes would I need?

Anode/cathode refers to pins of the LEDs.
Current flows from the anode (+) to the cathode (-).