Could the sky on a planet theoretically be any color?

This is an extremely hard question to answer definitely; its answer is heavily dependent on three things (1) the makeup of the atmosphere in question (2) the density of the atmosphere in question and (3) the surface temperature, and therefore the spectrum of output light, of the star in question.

If the atmopsphere's gasses are themselves are coloured (e.g. $N\,O_2$), then such gasses can clearly shift an atmosphere's colour greatly. In low density atmospheres, such as that of Mars, dust and matter swept up from the surface dominates, giving the sky a "butterscotch" colour. We clearly need to know what's floating around, so we can't say much more about point (1), so I shall now assume in this answer that the gasses in the atmosphere themselves are uncoloured.

In this case, the dominant effect setting the colour is Rayleigh Scattering. This is the diffraction of light from smaller-than-wavelength inhomogeneities in the atmosphere. When you "see" the atmosphere, you are seeing scattered, not direct light from the sun in question, and Rayleigh scattering happens most strongly at shorter wavelengths. It is a powerful effect: in the small inhomogeneity limit, it varies as the inverse fourth power of the wavelength. So the process always favours shorter wavelengths.

This means that for a sun of similar spectrum to ours, and in an atmospheric density like ours, the sky will be blue, like ours, or like Jupiter's (in the upper layers). However, for very high density atmospheres, the direct light reaching the surface has its shorter wavelengths heavily attenuated by Rayleigh scattering, so that only longer wavelengths reach the surface. It is for this reason that pictures taken by Russia's Venera landers on Venus suggest that the sky has an orange glow.

If the planet is orbitting a red giant, I am guessing this would probably mean a greenish or yellow sky for a planet with an atmospheric density like ours, as the spectrum of the star's light contains only longer wavelengths than that from our Sun. However, the inverse fourth power dependence means that now the glow from the atmospheric gasses themselves is much weaker, so the sky's colour is more likely to be dominated by things like dust, as in the case of Mars.

The most common colour for the sky on Earth is a white (or rather grey) sky. Clouds cover around 70% of the Earth, and the nature by which they are scattering shortwave radiation makes them appear white or grey. This is because photons coming from the Sun are likely to be scattered multiple times, and because the dependence on wavelength is not strongly increasing or decreasing.

White sky over Llyn Padarn. Source: Wikimedia Commons

Blue skies are particularly frequent on Earth:

Blue sky. Source: Wikimedia Commons

Around sunset, we often have red skies:

Sunset sky. Source: deviantart.

That leaves a number of other colours. You mention green, black, brown. Black skies occur at night or when there is dense, heavy particulate matter in the atmosphere, such as smoke. One way to obtain a green sky is by Aurora. One could speculate a planet where those are semi-permanent.

Aurora. Source: Wikimedia Commons

Aurora, by the way, can also be red or yellow. However, aurora colours are limited by emission lines of upper atmospheric gases, which are usually relatively simple molecules. And perhaps by mixing of those colours. But they cannot be /any/ colour.

But combining those effects? If one can design an atmosphere from scratch, with a plausible way of this atmosphere to exist somewhere in the universe, with clouds at a particular density, aurorae dancing in the sky, aerosols perpetually present... you can create a lot of different colours. The sky is the limit ;-)