Are RNA cleavage sites always polyadenylated?
This answer attempts to cover only the question of mRNA processing. It does not address the polyadenylation of non-coding RNAs.

As far as I can see from the recent review by Neve et al. (2017) cleavage and polyadenylation are tightly coupled. It is interesting, in this regard, that histones mRNAs which lack polyA tails, have a different structure, lacking the canonical AAUAAA, at their 3ʹ ends (see review by Marzluff et al.).

As distinct enzyme activities are involved in cleavage and polyadenylation, it would, I imagine, be possible (either genetically or chemically) to disrupt the protein complex responsible for polyadenylation and hence prevent it occurring (this has probably been done). However this would not be physiologically relevant.

There is an earlier review by Tian and Graber (2007) of the sequence requirements of the cleavage site which makes no distinction between cleavage and polyadenylation.

However this is not my field, so others may have additional information I have missed.