Actually, I don't have anything to tell yet (because I don't know the gory details behind the blockchain protocol), but since the time between tx confirmations seems to be pretty damn random, then yes, the blockchain could be used as an RNG. I think about (the possibility of) implementing something like a dice site in a fully decentralized manner which would be absolutely fair with a zero "house edge"...
I guess the private keys could be generated by and saved inside the blockchain itself (or, rather, distributed across it), so that the winner could see them and thereby take the reward. So I don't think that "the other side" is actually necessary...