Is perfectly monochromatic light always polarized and vice-versa? Is perfectly monochromatic light always polarized and polarized light always monochromatic? I am not totally sure but I think that the answer to the first is 'YES'. Because if a radiation is unpolarized, its polarization changes randomly with time so that a Fourier analysis would immediately tell us that it composed of many frequencies. What about polarized light? Does it have to be monochromatic? If no, please give a counterexample.
 A: TL;DR: Monochromatic light can be unpolarized and polarized light can be non-monochromatic. My answer thus somewhat disagrees with the one by @RogerWood and I will give more details in the following.

(This answer has been edited completely upon request, to make it more accessible to a general audience.)
Let's look at the two cases.

*

*Polarized can easily be non-monochromatic. Simply take polarized light of multiple wavelengths and superimpose it.

*Monochromatic light can also be unpolarized. To understand this, we require some more detail.

Unpolarized monochromatic light
In quantum mechanics, light can be in a statistical mixed state between two polarizations. Mathematically, this is described by a density matrix $\rho$. For example, a unpolarized monochromatic state could be written
$$ \rho = \frac{1}{\sqrt{2}}\left( |1_{\omega,\mathrm{y-polarized}}\rangle\langle1_{\omega,\mathrm{y-polarized}}| + |1_{\omega,\mathrm{z-polarized}}\rangle\langle1_{\omega,\mathrm{z-polarized}}|\right) \,,$$
where $|1_{\omega,\mathrm{y-polarized}}\rangle$ is a single photon state at frequency $\omega$ that is linearly polarized in $y$-direction.
The above density matrix then represents a 50-50 statistical mixture of $y$- and $z$-polarized photons. It is clearly monochromatic (all photons contained have the same energy). And it is also unpolarized because you have a 50-50 chance of measuring either polarization.
What happens if this state is sent through a linear polarizer?
If this state is sent through a linear polarizer, you have a 50-50 chance of a polarized photon coming out at the other end. If you have many (uncorrelated) such photons, then half of them will go through, as we expect for unpolarized light.

Another edit to address seeming contradictions
There has been a lot of discussion concerning my answer. In particular, the answer by @A.P. gives a nice argument which seemingly proves my statement wrong. In the following, I will show that the argument by A.P. only applies to classical field amplitudes and does not account for quantum states of the electromagnetic field. As a consequence, my point still stands unlike stated in other answers.
The central argument in A.P.'s answer is:

Strictly speaking, the off-diagonal elements of unpolarized light must be 0 for all frequencies . This is only possible if for any given frequency  either () or () is 0. Because unpolarized light must contain equal power in its  and  components it must have at least 2 distinct frequencies, like ()=(−), =(−). Therefore it can't be monochromatic.

The second sentence is not true for general quantum states, which I will demonstrate in the following by computing the expectation value for a quantum state that contradicts this statement.
Consider the state which contains two photons at frequency $\omega$, one polarized along $x$ and one polarized along $y$. We can write this state as $|\psi\rangle = |1_x(\omega)\rangle|1_y(\omega)\rangle$. Now let us compute the off-diagonal expectation value in A.P.'s answer, where $E_x(\omega)$ and $E_y(\omega)$ now have to be the electric field operators at frequency $\omega$ projected along the respective polarization directions. A sketch of the computation is as follows:
$$ \langle \psi | \hat{E}_x\hat{E}_y|\psi\rangle\propto \langle \psi | [\hat{a}^\dagger_x(\omega)-\hat{a}_x(\omega)][\hat{a}^\dagger_y(\omega)-\hat{a}_y(\omega)]|\psi\rangle\\ = \langle 1_x(\omega) | \hat{a}^\dagger_x(\omega)-\hat{a}_x(\omega)|1_x(\omega)\rangle^2
= 0 \,.$$
We have a single frequency, so according to A.P.'s argument, this should be non-zero, since our quantum state contains photons which are polarized along $x$ and photons which are polarized along $y$. However, it is zero! What happened here?
The point is that A.P.'s argument relies on classical field amplitudes and their statistics. His answer thus raises a relevant restriction with regards to classical fields, but it is incomplete for quantum states of the electromagnetic field. For Fock states, we can populate different polarization directions without this being the same state as photons along the average direction. This is the core difference to the classical treatment.
A: In short: There is a lower limit on the spectral width $\Delta \omega$ of unpolarized light. Therefore, strictly monochromatic unpolarized light can not exist, not even mathematically, while spectrally broad unpolarized and polarized light exists.
The following holds for classical light which has a well-defined electric field at each point in spacetime. An equivalent formalism is still to be developed for quantum mechanical states.[1, 2] Have a look at Wolpertinger's answer to see how a nonclassical state like $|1_{x, \omega}\rangle |1_{y, \omega}\rangle$ can fulfill the classical criteria for unpolarized light and be monochromatic at the same time.

A very good description why unpolarized light must have a minimum bandwidth is given in E. Wolf, Phys. Lett. A 312 (2003). Imagine a beam propagating along the $z$-axis. It can have polarization components along the $x$- and $y$-axis $E_x (\vec{r}, \omega)$, $E_y (\vec{r}, \omega)$. The author defines the so-called cross-spectral density matrix (eq. 1)
$$
\underline{\underline{W}} \left( \vec{r}_1, \vec{r}_2, \omega \right) = \left( \begin{matrix}
\left\langle {E_x}^* (\vec{r}_1, \omega) \, E_x (\vec{r}_2, \omega) \right\rangle &
\left\langle {E_x}^* (\vec{r}_1, \omega) \, E_y (\vec{r}_2, \omega) \right\rangle \\
\left\langle {E_y}^* (\vec{r}_1, \omega) \, E_x (\vec{r}_2, \omega) \right\rangle &
\left\langle {E_y}^* (\vec{r}_1, \omega) \, E_y (\vec{r}_2, \omega) \right\rangle
\end{matrix}\right) \text{,}
$$
which combines information about the spectral and polarization-coherence. For our purposes we can set $\vec{r}_1 = \vec{r}_2 = \vec{r}$ and omit this argument. For the sake of clarity let me write down the simpler version:
$$
\underline{\underline{W}} \left( \omega \right) = \left( \begin{matrix}
\left\langle {E_x}^* (\omega) \, E_x (\omega) \right\rangle &
\left\langle {E_x}^* (\omega) \, E_y (\omega) \right\rangle \\
\left\langle {E_y}^* (\omega) \, E_x (\omega) \right\rangle &
\left\langle {E_y}^* (\omega) \, E_y (\omega) \right\rangle
\end{matrix}\right) \text{,}
$$
The diagonal elements are quite straightforward to understand: $\left\langle {E_x}^* (\omega) \, E_x (\omega) \right\rangle$ is the spectral power density the beam contains at frequency $\omega$ in the $x$ polarization component, and analogously for $y$. As of equation (4) of the paper the overall spectral density is given by
$$
S (\omega) = \text{Tr} \left( \underline{\underline{W}} \left( \omega \right) \right) = \left\langle {E_x}^* (\omega) \, E_x (\omega) \right\rangle + \left\langle {E_y}^* (\omega) \, E_y (\omega) \right\rangle \text{.}
$$
The off-diagonal elements are the cross power spectral densities between the orthogonal polarization components, which describes their correlation. Strictly speaking, the off-diagonal elements of unpolarized light must be $0$ for all frequencies $\omega$. This is only possible if for any given frequency $\omega$ either $E_x (\omega)$ or $E_y (\omega)$ is $0$. Because unpolarized light must contain equal power in its $x$ and $y$ components it must have at least $2$ distinct frequencies, like $E_x (\omega) = \delta (\omega - \omega_x)$, $E_y = \delta (\omega - \omega_y)$. Therefore it can't be monochromatic.

For practical purposes unpolarized light can be defined less strictly. If we switch to the time-domain we will find that light with cross power spectral density of finite width $\Delta \omega$ has a cross-polarization correlation
$$
R_{xy} (\tau) = \left\langle {E_x}^* (t - \tau) \, E_y (t) \right\rangle_t
$$
which tends to $0$ on timescales of the inverse bandwidth $1 / \Delta \omega$ (see Wiener-Khinchin theorem). For longer timescales $\tau \gg 1/ \Delta \omega$ the light appears unpolarized, because there is no correlation between the direction of the electic field vector at time $t$ and at time $t + \tau$. 
For a given cross power spectral density $\left\langle {E_x}^* (\omega) \, E_y (\omega) \right\rangle$ the narrowest possible overall power spectral density $S(\omega)$, therefore the 'most monochromatic' light, is when the $x$ and $y$ component have the same spectrum $\left\langle {E_x}^* (\omega) \, E_x (\omega) \right\rangle = \left\langle {E_y}^* (\omega) \, E_y (\omega) \right\rangle$. Hence, also the overall spectrum $S(\omega)$ has a bandwidth of $\Delta \omega$. Again, applying the Wiener-Khinchin theorem we can state that the light appears to be monochromatic on timescales shorter than the coherence time $\tau_c \approx 1 / \Delta \omega$. The conclusion is that the light appears polarized on the same timescale as it appears monochromatic. There is no timescale on which light can appear unpolarized, but still monochromatic.
A: You are correct, but the light does have to be really really monochromatic and the polarization has to be strictly defined and exactly fixed.  
As you point out, if you examine the light through a fixed polarizing filter and if its amplitude changes over some period of time, then there must be more than one frequency present. Polarization can be linear or circular or something in between, but must be fixed for the duration. The length of the observation and the amount of change that can be measured obviously limit the degree to which you can claim only a single frequency is present.  
[ To be fair, 'monochromatic' would usually be interpreted to mean a very narrow band of frequencies, as from a laser, rather than just one frequency.  Strictly, a single frequency necessarily lasts unchanged for an infinite length of time ]  
Polarized light is not necessarily monochromatic.  A single beam may contain two wavelengths (frequencies) both with the same well-defined fixed polarization. 
[Edit] The emission or measurement of a single photon is a quantum-mechanical event associated with a certain region of spacetime.  As such it cannot be strictly monochromatic.  By definition a single frequency would occupy all of spacetime. 
Nothing in the real world can be considered purely monochromatic
