Haces una lista de colores y luego tomas 2 en modo random, pintas la mitad de los pixeles de un color y la otra de otro dentro de un Enumerador y luego lo llamas desde una corrutina y ya esta!

Utilizando el color Background de la cámara y una textura transparente desde un sprite o un malla tipo plano.
 
Luego modificas el color del Background de la cámara y del material de la textura.
 
 
 
Enlace de descarga 2D: http://www.speedyshare.com/ca8za/cambiocolor.unitypackage
 
 
 
Pero esto sería para crear un efecto 2D, donde utilizas un plano o un sprite.
 
 
 
Si quieres un efecto 3D, tienes que crear un SkyBox con texturas en blanco y negro, en escala de grises. Aquí tienes un ejemplo de Skybox en escala de grises: http://creacionvideojuegos.foroactivo.com/t58-escenario-ambiente-realista
 
 

Creo que es mas óptimo hacerlo con un shader directamente.
 
Para modificar los colores y los valores del remap, que le he puesto para controlar un poco el degradado de un color a otro, solo tienes que usar "renderer.material.SetColor("_color1", Color.red)" o "renderer.material.SetFloat("_remapMin", floatValue)".
 

Shader "Custom/Gradient" {
    Properties {
        _color1 ("Color1", Color) = (1,0,0,1)
        _color2 ("Color2", Color) = (0,0.8758622,1,1)
        _remapMin ("RemapMin", Float ) = 0.36
        _remapMax ("RemapMax", Float ) = 0.68
    }
    SubShader {
        Tags {
            "RenderType"="Opaque"
        }
        Pass {
            Name "FORWARD"
            Tags {
                "LightMode"="ForwardBase"
            }
            
            
            CGPROGRAM
            #pragma vertex vert
            #pragma fragment frag
            #define UNITY_PASS_FORWARDBASE
            #include "UnityCG.cginc"
            #pragma multi_compile_fwdbase_fullshadows
            #pragma multi_compile_fog
            #pragma exclude_renderers gles3 metal d3d11_9x xbox360 xboxone ps3 ps4 psp2 
            #pragma target 3.0
            uniform float4 _color1;
            uniform float4 _color2;
            uniform float _remapMin;
            uniform float _remapMax;
            struct VertexInput {
                float4 vertex : POSITION;
                float2 texcoord0 : TEXCOORD0;
            };
            struct VertexOutput {
                float4 pos : SV_POSITION;
                float2 uv0 : TEXCOORD0;
                UNITY_FOG_COORDS(1)
            };
            VertexOutput vert (VertexInput v) {
                VertexOutput o = (VertexOutput)0;
                o.uv0 = v.texcoord0;
                o.pos = mul(UNITY_MATRIX_MVP, v.vertex);
                UNITY_TRANSFER_FOG(o,o.pos);
                return o;
            }
            float4 frag(VertexOutput i) : COLOR {
                float3 emissive = lerp(_color1.rgb,_color2.rgb,(_remapMin + ( (i.uv0.r - 0.0) * (_remapMax - _remapMin) ) / (1.0 - 0.0)));
                float3 finalColor = emissive;
                fixed4 finalRGBA = fixed4(finalColor,1);
                UNITY_APPLY_FOG(i.fogCoord, finalRGBA);
                return finalRGBA;
            }
            ENDCG
        }
    }
    FallBack "Diffuse"
}

 
 

este asset esta bueno para crear gradientes: https://www.assetstore.unity3d.com/en/#!/content/51733