Puedes usar JS (que no es JAVA, ni realmente es JQuery).
Lo que no estás explicando es bajo que condiciones se asigna (o se cambia) el color. Ni entre cuáles.
[edit]
En realidad, las animaciones de CSS usan javascript, pero están por detrás.
Y acá hay algo que no es totalmente CSS, como no das más datos no sé si te servirá estudiarlo.
Random Color CSS3 Animation
Quien más sabía de todo esto ya no viene al Foro, así que vamos a ver si aparece alguna idea por otro lado.
[/edit]