Does all EM radiation consist of photons?

Generally speaking, all electromagnetic radiation can be reduced to being a combination of "photons."

When the light can be represented as a clean wave, $\mathbf{E}(t) = \mathbf{E}_0 \cos{\omega t}$, as we expect classically, then the light is a "coherent state" which has a Poissonian distribution in photon number (and technically as @aekmr points out, for it to be a coherent state the "noise", ie fluctuations, of the electric field needs to be normally distributed without changing as it propagates). So if you put a detector that could measure exactly the total number of photons for this coherent state, you would find that the probability of measuring a certain photon number is:

$$P(n)=\frac{\bar{n}^{n} e^{-\bar{n}}}{n !}$$

with $\bar{n}$ being the mean photon number (which doesn't need to be an integer). This visually looks like this:

If you notice it is a bit counter intuitive, basically any classical light is uncertain in its photon number. It's possible to get more "sharp" distributions with more photon number certainty called "sub-Poissonian", but these require special quantum effects.

I should also point out that (mentioned by @aekmr) classically you can also get "thermal light" (in the class called "super-poissonian" statistics) which has a different fatter distribution in photon number - and it looks like the one labeled here as a Bose-Einstein distribution:

To take an extreme example, if I charge something, say a metal sphere, and then 'wave it about', I will generate EM radiation - will that radiation consist of photons?

It certainly will radiate "photons," and in principle we could measure how many photons it has either by using (a lot of) number resolving detectors or by detecting the electric field and looking at the statistics of its values.

(Also, I'm pretty sure that these photons will be "coherent states," but I'm not exactly sure how to prove it though.)

EDIT:

Maybe this answer is a bit too simple, as @aekmr suggests, so I'll try to answer some more technical points about it.

Generally speaking, the quantum state of light of an electric field can be broken down into the "Fock state basis" (which is basically the basis that tells you how many photons your state is in). For example, your state might be a superposition of being in vacuum, one photon, and two photons, (like this $|\psi\rangle = c_1|0\rangle + c_2|1\rangle +c_3|2\rangle$).

Combinations of these superpositions produce both the average value of the electric field that you will measure and the statistics that you observe (so if you were to take the same state and measure the electric field multiple times, you'll observe a particular distribution for the values of the electric field). And also as a technical point, sometimes, like in the case of thermal light, the photons are not actually in "superpositions" but are just a mix of different photons that are entering your detector with certain probabilities.

In the case where you get a clean sine wave and when the distribution (in the electric field) as it propagates looks is a gaussian distribution, then you have a coherent state as your underlying state. As a visualization, this is what a coherent state looks like in time:

Then you can use the strength of the amplitude relative to the noise to infer the mean photon number for this coherent state.

In the case where your light does not follow this expected classical behavior, then you might have an unusual superposition of photons - and these can give you all sorts of funky statistics in the strength of the electric field. For instance while a single photon is just a single "click" in a "single-photon-detector" - if you were to look at the strength of the electric field for a photon, you would see that it has an unusual statistical distribution:

Which strangely shows that a single photon's average E-field value is zero! I should add here that while it seems trivial to make photons from your example, creating a perfect single photon is very challenging and is an active field of research.

Photons are what light is and they can have frequencies anywhere from radio to gamma. Billions of coherent photons resemble a wave.

TL;DR: Yes: every kind of electromagnetic radiation is made by photons.

In Quantum Mechanic and in Quantum Field Theory forces, such as the electric force are carried through space by quantum particles called bosons. (The adjective quantum in the term quantum particle is not a decorative one, it is important: in fact quantum particles are almost nothing like classical particles and you should keep it in mind; picturing photons as little balls could rapidly lead you to mistakes). An electromagnetic wave is nothing more that the manifestation of the electric and magnetic force acting at a distance, so our theory states that it is made up by bosons, specifically photons since we are dealing with electromagnetism.