driver - How can I effectively drive multiple LEDs with multiplexing?

I am interfacing my microcontroller (AVRmega32U4) to a 4x4 LED array. There are 2 control lines to operate columns (passed to a 2 to 4 demultiplexer) and 4 control lines to operate rows. I bring a column high and a row low to illuminate a specific LED. I pull either the column low or the row high to turn off an LED.

This design works fine for around up to 4 LEDs at once. However, when I try to light all 16 at once with this strategy, the LEDs are noticeably less brighter (they're on a 1/16 duty cycle after all!).

What are some ways to more effectively light larger numbers of LEDs in this array? Say, 10+?

I am considering writing a lot of code to handle the different situations, but that will consume more space on my microcontroller than I am comfortable with. I was considering adding another micro with 16 control lines to manage these LEDs, one at a time, but this seems like a lot of overhead to introduce.

Answer

I used valuable information from Telaclavo's answer to adjust mine. If you like his, don't forget to upvote him.

If your duty cycle is 1/16 then you would have to give each LED 16x its nominal current to get the same average brightness. This will decrease your LEDs' life. High brightness LEDs can be PWM controlled at their nominal current at 1/16 duty cycle and still be as bright as a common indicator LED.
The easiest solution is to keep that duty cycle fixed, so that you can also have the current fixed. Each column driver will have to drive 4 LEDs simultaneously, so that's 4 times nominal current.

The 7404 you have in your schematic is not suited for this. First TTL can source very little current: 0.4mA. But even sinking won't do, that's also only 16mA, most LEDs, also high brightness are specified for 20mA. You need a driver which can source that. In your 4 columns x 4 rows each of the 4 columns has to supply 4 LEDs with 20mA each, that's 80mA. There exist high side drivers, but you may have to work with discrete components (BJT or MOSFET). The current won't result in a high dissipation, since its average per high side transistor is only 1/4 of that: 20mA, and that's worst case, if all LEDs are on.

edit
A BC807 is a good choice for this, and has an \$H_{FE}\$ of 100 minimum, so that a few mA of base current will drive it in saturation. You don't need the 7404 anymore to invert the active low output from the 74S139, since the BC807 is driven by a low voltage. The 74S139 (why not LS?) can sink the required current, also a 74HC139 will do.
While most microcontrollers are able to sink 20mA, this doesn't seem the case for the ATMega32U4. The datasheet doesn't give maximum current as a parameter (a lacune), but minimum and maximum output voltage are specified at 10mA. So for the low side you'll an extra driver. The 74LVC07A is specified for sinking currents to 32mA.

In quantities the 74HC139 + 74LVC07A + 4 \$\times\$ BC807 + 8 resistors cost less than 35 cent at Digikey.