There are no continuous solutions. Since the cosine has a unique fixed point $x_0$ (such that $\cos x_0=x_0$), it should be a fixed point of f. And f should be injective and hence monotone (increasing or decreasing) in a neighborhood of $x_0$. Then f(f(x)) is increasing in a (possibly smaller) neighborhood of $x_0$ while the cosine is not.
As for discontinuous ones, there are terribly many of them ($2^{\mathbb R}$) and you probably cannot parametrize them in any reasonable way. You can describe them in terms of orbits of iterations of $\cos x$, but I doubt this would count as a solution of the equation.
UPDATE: Here is how to construct a solution (this is technical and I might overlook something).
Let X be an infinite set and $g:X\to X$ is a map, I am looking for a sufficient conditions for the existence of a solution of $f\circ f=g$. Define the following equivalence relation on X: x and y are equivalent iff $g^n(x)=g^m(y)$ for some positive integers m and n. Equivalence classes will be referred to as orbits (the term is wrong but I don't know what is a correct one). Two orbits are said to be similar is there is a bijection between them commuting with fg. If Y and Z are two similar orbits, one can define f on $Y\cup Z$ as follows: on Y, f is that bijection to Z, and on Z, f is the inverse bijection composed with fg.
So if the orbits can be split into pairs of similar ones, we have a desired f. Now remove from the real line the fixed point of cos and all its roots ($\pi/2$ and the like). Then, if I am not missing something, in the remaining set X all orbits of cos are similar, so we can define f as above. Define f so that 0 has a nonempty pre-image (that is, the orbit containing 0 should be used as Z and not as Y). Finally. map the fixed point of cos to itself, and the roots of cos to some pre-image of 0.
