Maximum number of materials that can be added in a scene?
Use the same material for every object but have different colors for it.

I assume you will generate this dynamically. Some methods I can think of:


Generate a 4096x4096 texture and assign that. Use nearest interpolation (like in minecraft). Have each planes UV-coordinates point out what pixel to use.
Use vertex colors for each plane. Have the material use the the vertex colors. Use the attribute node: http://wiki.blender.org/index.php/Doc:2.6/Manual/Render/Cycles/Nodes/More#Attribute
If you don't need exact colors, if you are content with a random color, use the object info node to get a random value for each node, insert it into a color ramp node.