How to drive 4000 LEDs using as few pins as possible?
Addressable WS2812 LEDs may be what you require. These are used in indicators and common LED strips.



Figure 1. Individually addressable LEDs. Source: Espruino.com.



Figure 2. Strip version.

See Sparkfun WS2812 datasheet for details on communicating with these.

I'm not familiar with these ones but a quick scan of the datasheet reveals


  When the refresh rate is 30fps, low speed model cascade number are not less than 512 points, high speed mode not
  less than 1024 points.


That means you could control them all with four micro output pins.



From the comments:


  Unfortunately, the system I need will have them split into 40 10x10 disparate arrays (1mm LEDs).


The arrays can be daisy-chained. The protocol is effectively a one-wire bus. Data is transmitted with values for the nearest chip first. It strips off its data and passes everything else along the line. Each successive chip thinks it is first in line and strips off the first values and passes the rest along.