Why is the sky never green? It can be blue or orange, and green is in between! I, like everybody I suppose, have read the explanations why the colour of the sky is blue:

... the two most common types of matter present in the atmosphere are
  gaseous nitrogen and oxygen. These particles are most effective in
  scattering the higher frequency and shorter wavelength portions of the
  visible light spectrum. This scattering process involves the
  absorption of a light wave by an atom followed by reemission of a
  light wave in a variety of directions. The amount of multidirectional
  scattering that occurs is dependent upon the frequency of the light.
  ... So as white light.. from the sun passes through our atmosphere,
  the high frequencies become scattered by atmospheric particles while
  the lower frequencies are most likely to pass through the atmosphere
  without a significant alteration in their direction. This scattering
  of the higher frequencies of light illuminates the skies with light on
  the BIV end of the visible spectrum. Compared to blue light, violet
  light is most easily scattered by atmospheric particles. However, our
  eyes are more sensitive to light with blue frequencies. Thus, we view
  the skies as being blue in color.

and why sunsets are red:

... the light that is not scattered is able to pass through our
  atmosphere and reach our eyes in a rather non-interrupted path. The
  lower frequencies of sunlight (ROY) tend to reach our eyes as we sight
  directly at the sun during midday. While sunlight consists of the
  entire range of frequencies of visible light, not all frequencies are
  equally intense. In fact, sunlight tends to be most rich with yellow
  light frequencies. For these reasons, the sun appears yellow during
  midday due to the direct passage of dominant amounts of yellow
  frequencies through our atmosphere and to our eyes.
The appearance of the sun changes with the time of day. While it may
  be yellow during midday, it is often found to gradually turn color as
  it approaches sunset. This can be explained by light scattering. As
  the sun approaches the horizon line, sunlight must traverse a greater
  distance through our atmosphere; this is demonstrated in the diagram
  below. As the path that sunlight takes through our atmosphere
  increases in length, ROYGBIV encounters more and more atmospheric
  particles. This results in the scattering of greater and greater
  amounts of yellow light. During sunset hours, the light passing
  through our atmosphere to our eyes tends to be most concentrated with
  red and orange frequencies of light. For this reason, the sunsets have
  a reddish-orange hue. The effect of a red sunset becomes more
  pronounced if the atmosphere contains more and more particles.

Can you explain why the colour of the sky passes from blue to orange/red skipping altogether the whole range of green frequencies?
I have only heard of the legendary 'green, emerald line/ flash' 

that appears in particular circumstances

Green flashes are enhanced by mirage, which increase refraction... is more likely to be seen in stable, clear air,... One might expect to see a blue flash, since blue light is
  refracted most of all, and ... is
  therefore the very last to disappear below the horizon, but the blue
  is preferentially scattered out of the line of sight, and the
  remaining light ends up appearing green

but I have never seen it, nor do I know anybody who ever did.
 A: I scrolled through the answers expecting to find at least one with a chromaticity diagram, but there are none, so I'm writing my own.
Short answer: it simply isn't true that colors are arranged in a line and that to get from blue to orange one must go through green. It isn't true of psychological colors, nor is it true of physical colors (electromagnetic waves).
Here's a CIE xy chromaticity diagram with the approximate location of sky blue and "sky orange" circled.

(I made this by finding some photos of the sky online that looked realistic, using an eyedropper tool on them, converting the sRGB colors to CIE xy, and then placing the circles by hand. I have normal color vision and I used an IPS monitor with accurate sRGB color, but still, the circles should be considered very approximate.)
CIE xy coordinates are rational linear functions of the physical spectrum, which means that linearly interpolating between two physical spectra gets you only the perceptual colors lying on the straight line segment between those colors on the xy diagram. So, supposing that the transition from midday to dusk is roughly linear, we'd expect the intermediate colors to be in the pinkish range, on the opposite side of the white point from green. A small deviation from linearity could produce a pale green, but it would take a large nonlinearity to get a highly saturated green.
You can also understand this by thinking about the spectra directly. The spectrum of sky blue has (compared to neutral white) more light at high frequencies, less at low frequencies, and an intermediate amount at intermediate frequencies. The spectrum of sky orange is roughly the reverse of that. There are not many processes in nature that change the frequency of light, and none of them are involved in determining the color of the sky, so when you model the smooth transition from one of these spectra to the other, you should model it as acting independently on each frequency. When going from blue to orange, the high frequencies start out bright, end up dim, and are in between in between. The low frequencies are the other way around. The middle frequencies start out at medium intensity, end at medium intensity, and are probably at medium intensity in between. Thus, the midway point between the peak at violet and the peak at red isn't a peak at green; it is, rather, a more or less flat spectrum. It could have enough of a peak in the middle to appear as pale green, or enough of a trough to appear as pink, but there's no reason to expect a bright green (or bright magenta).
The only way you could plausibly get a bright perceptual green in the atmosphere is by frequency-dependent diffraction, the same phenomenon that gives you rainbows. This is what causes green flashes, as you can see in Andrew Young's lovely simulations, particularly this one.
There is one physical phenomenon in which a smooth transition from bright blue to bright orange does go through bright intermediate rainbow colors, and that's Doppler shift. But a Doppler shift of that magnitude requires relative speeds that are a substantial fraction of the speed of light. That isn't what happens in the atmosphere.
A: The sky does not skip over the green range of frequencies. The sky is green. Remove the scattered light from the Sun and the Moon and even the starlight, if you so wish, and you'll be left with something called airglow (check out the link, it's awesome, great pics, and nice explanation).
Because the link does such a good job explaining airglow, I'll skip the nitty gritty.
So you might be thinking, "Jim, you half-insane ceiling fan, everybody knows that the night sky is black!" Well, you're only half right. The night sky isn't black. The link above explains the science of it, but if that's not good enough, try to remember back to a time when you might have been out in the countryside. No bright city lights, just the night sky and trees. Now when you look at the horizon, can you see the trees? Yes, they're black silhouettes against the night sky. But how could you see black against black? The night sky isn't black. It's green thanks to airglow (or, if you're near a city, orange thanks to light pollution).
Stop, it's picture time. Here's an above the atmosphere view of the night sky from Wikipedia:

And one from the link I posted, just in case you didn't check it out:

See, don't be worried about green. The sky gets around to being green all the time.
A: The sun is technically green because the peak of its black body spectrum is near green wavelengths.  When light scatters parallel to the plane of incidence (i.e., during the day time), it is blue-shifted.  When light scatters perpendicular to the plane of incidence (i.e., sunset or sunrise), it is red-shifted.  The light that is not scattered but makes it effectively straight through is not shifted in wavelength.  One of my astronomy professors explained that the reason the sun appears yellow to us (and not green) is largely due to the response of our eyes.  Regardless, the when sunlight is scattered it tends to move away from green since most of it is already green.
(fun side note:  plants used to be red, thus absorbing more green light… though I forgot now why they evolved to be green and now reflect most sunlight)
The image 1 shows the solar spectrum with the visible light portion shown in color.  The image can be found here.

A: Note well: What we perceive as color is bit of a tricky subject. This is a different question, one that has been asked and answered multiple times at this site. Per the typical human eye response, sunlight at the top of the atmosphere is about as "white" as "white" can be.
Some of that incoming sunlight is reflected back into space, some is absorbed by the atmosphere, and some is scattered by the atmosphere. There are two main kinds of scattering: Rayleigh scattering, which selective scatters high frequency light (violet and blue) much more than low frequency light (red), and Mie scattering, which scatters light more or less evenly across the spectrum. Rayleigh scattering is a clear sky phenomenon. Mie scattering results when small droplets of water are suspended in the air (e.g., clouds).
The sky is blue at noon on a clear day because of Rayleigh scattering. The atmosphere selectively refracts the violet/blue end of the spectrum. After undergoing a large number of such refractions, some of that refracted light comes down to the ground. The result: A blue sky. Note that we would see a white Sun against a black background if this refraction did not occur. This is what astronauts and cosmonauts see in space.
At sunrise and sunset, the violet, blue, and green parts of the incoming sunlight are almost gone. The result: We see a quite reddish sun. We still see a predominantly blue sky even at sunrise and sunset. It's only at the horizon where we see a reddish colored sky. Rayleigh scattering does affect red light as well, just not as strongly. That red colored sky is partly a result of Rayleigh scattering. The high wavelength light has been scattered away. The red light, to a much lesser extent. The reddish sunlight that makes it through hundreds of kilometers of sunrise/sunset sky is eventually scattered as well, so we see that reddish light as a reddish sky. A slightly cloudy makes for even better sunrises and sunsets because now Mie scattering can occur as well. Mie scattering can spread that incoming reddish sunlight across a good portion of the horizon sky.
With regard to green, you can see a greenish sky at sunrise/sunset. There oftentimes is a narrow band between the blue sky away from the horizon and the red sky at the horizon where the sky appears greenish.


The above is a clear sky phenomenon, and it's only a narrow band of the sky that appears green. An infrequent event can occur where the entire sky appears green. This is called a green thunderstorm. This happens when a thunderstorm occurs at just the right time of day, with just the right height of clouds, and just the right lighting. This can make the entire sky rather than just a thin band appear to be grayish green, and sometimes very green.

Update: Green Flash
Here's a picture of a green flash:

Green flashes are a mirage. They are real effects; they are not an optical illusion.
There's a distinction between a mirage and an optical illusion. On driving along a black asphalt road on a clear, hot summer day, you may have seen the road ahead appear to be covered with shimmering water. That's a combination of a mirage (a real effect) and an optical illusion (your brain misinterpreting what you see). The real effect is that atmospheric refraction results in you seeing a reflection of the air on the road. The reflection is anything but even. The road is hot, so hot you might be able to fry an egg on it, and this results in atmospheric disturbances just above the asphalt. The result is that the reflection is rather uneven and changes over time. This makes the reflection appear to shimmer. The reflection and the shimmering: These are real effects. You can photograph them, you can explain them with physics. The optical illusion is that your brain misinterprets these real effects as shimmering water.
Green flashes are best seen where the Sun rises or sets over the ocean, for a number of reasons. One is the flatness of the horizon. You need to be able to "see" the Sun before it has risen / after it has set. Another is the high heat conductivity of water relative to land. This helps create local thermal variations near the surface (similar to the black asphalt described above).
One form of green flash occurs when the ocean surface is warmer than the air above. This results in an inferior-mirage flash that lasts about a second. It occurs just a moment after the top of the Sun appears to have slipped below the horizon at sunset or just a moment before the top of the Sun will appear at sunrise.
Another form of green flash occurs when the ocean surface is cooler than the air above. This results in a mock-mirage flash than lasts about a second. These occur just a moment before the top of the Sun will appear to slip below the horizon at sunset or just a moment after the top of the Sun appears at sunrise.
A third form occurs when there is a strong atmospheric temperature inversion above the observer. This results in a sub-duct flash, where a sometimes sizable portion of the Sun appears to pinch off the setting/rising Sun and turn green. This form lasts significantly longer than the first two forms.
A number of photographs have been taken of all three of the above forms. There is one last form of green flash, the very rare and very short lived green ray that appears to emanate from the top of a green flash. A number of reputable observers have reported this phenomenon, so apparently it is real. However, no reputable observer has yet caught this phenomenon in a photograph.
A: The accepted airglow answer might be technically true, but it does not answer the question! The existence of an additional and very faint source of green light in the atmosphere does not explain the absence of the green light in the sunset sky gradient.
I wasn't satisfied with other answers either. The only satisfactory answer I could find is this one. Below I explain it in my own words and add my own details. Treat this answer as a personal opinion and not a source of truth.
So there are two main factors that contribute to the blue color for the sky at day and red at sunset.
The first one is Rayleigh scattering. The sunlight contains all colors, but they scatter in different amounts:

Blue is the first to scatter, so the sky normally is blue.
The second factor is that the thickness of the atmosphere is uneven when measured from a point on the ground to the zenith and from the same point on the ground to the horizon:

The closer the sun gets to the horizon, the longer path does the light take through the thickness of the atmosphere. The longer the path, the more other colors get scattered.
But the farther a color is from blue in the spectrum, the more it tends to follow a straight path through the thickness of the atmosphere. Red is the toughest: even when it scatters, it scatters at small angles. Thus, you can see red only around the sun because that's where the angles are the smallest.
But every color scatters at it's own angle, not just blue and red. This means that we should see a rainbow-like gradient on the sunset sky, but we don't. Why?
The matter is that the green is always there, but it's never there alone. It's always mixed either with red (forming yellow) or blue (forming turquoise).
Thus, the sunset gradient is as follows: R-RG-GB-B, that is red-yellow-turquoise-blue. And that is indeed the gradient we see in the sky. The blue color of the evening sky is not purely blue, it's turquoise.
But our eyes and brain perform color correction and still identify it as blue. We have no color reference when we look at the sky. If you had a pure blue color object in your hand and compared the color to the color of the blue sky close to the yellow part, you'll notice that the sky is not blue but rather turquoise (or even aquamarine, see photos below).
But why is green a dirty (mixed) color and red and blue are pure colors in that gradient? That makes no sense. They should then be all mixed?
Well, the answer is that red and blue are at the ends of the gradient and they have nothing to mix with. Here's the graph of colors vs intensity in the sun spectrum:

If the sun's spectrum were wider (with large amounts of ultraviolet on the blue side and infrared on the red side) and our eyes could register those extra colors, the sunset gradient would be like this:
I-IR-RG-GB-BU-U, that is
infrared -- infrared-red -- yellow -- turquoise -- blue-ultraviolet -- ultraviolet.
See? This imaginary sky has no pure red and no pure blue.
Note that even the red color of the sunset sky is not technically pure red. It still contains some blue and green and all other intermediate colors. It's just the matter of which color(s) dominate.
And finally, sometimes you do actually see the green (aquamarine) color in the sunset gradient:
 
A: The hand waving explanation in your question is called Rayleigh scattering

Rayleigh scattering results from the electric polarizability of the particles. The oscillating electric field of a light wave acts on the charges within a particle, causing them to move at the same frequency. The particle therefore becomes a small radiating dipole whose radiation we see as scattered light.

The question then becomes why not see the sky as green rather than blue 

Rayleigh scattering is inversely proportional to the fourth power of wavelength, so that shorter wavelength violet and blue light will scatter more than the longer wavelengths (yellow and especially red light). However, the Sun, like any star, has its own spectrum and so I0 in the scattering formula above is not constant but falls away in the violet. In addition the oxygen in the Earth's atmosphere absorbs wavelengths at the edge of the ultra-violet region of the spectrum. The resulting color, which appears like a pale blue, actually is a mixture of all the scattered colors, mainly blue and green. Conversely, glancing toward the sun, the colors that were not scattered away — the longer wavelengths such as red and yellow light — are directly visible, giving the sun itself a slightly yellowish hue. Viewed from space, however, the sky is black and the sun is white.

Italics mine. Here color perception from the physiology of the retina enters, and it is not a physics question any longer, but a question of how the cones in the retina interpret the impinging spectral frequencies.

The reddening of sunlight is intensified when the sun is near the horizon, because the volume of air through which sunlight must pass is significantly greater than when the sun is high in the sky. The Rayleigh scattering effect is thus increased, removing virtually all blue light from the direct path to the observer. The remaining unscattered light is mostly of a longer wavelength, and therefore appears to be orange.

So  I presume we interpret "blue" even when green is mixed up  with it ( as we interpret white when all colors are mixed up) and it is a matter of perception. 
The green flash  can also be explained with scattering and the difference in the wavelengths between blue and green. Here is a link with photos included. I suspect that the physiology of the eye also plays a role in the perception.
It is interesting that the flashes are not always green , here is an interesting analysis of this refraction process.
