saftysign:
There are 2 control lines to operate columns (passed to a 2 to 4 demultiplexer) and 4 control lines to operate rows.
Then you should have a 4:1 multiplex, which should actually be bright enough, even with crappy LEDs.
You really should follow Grumpy_Mike's advice and reserve a memory buffer to control which LEDs are on, then offload the display to some timer interrupt and be done with it.
Also, read the link that Mike posted carefully and try to understand how a LED matrix actually works.
Alternatively, if this all proves too hard for you to implement, you could consider using dedicated drivers like the TLC5916 or some such. No shame in that, and it would definitely solve your brightness "problem"... 