Wouldn't this be illegal? It is the easy option, but I would advice against it. Both parties are wrong here. However, the op's is the lesser crime. In most jurisdictions, his is a simple misdemeanor offense and does not warrant jail time. Unless, there is more to this than the exchange is letting on, but i doubt it.

On the other hand, Changenow are guilty of false representation: Making affirmative statements that the exchange is anonymous and limitless, not needing an account and so forth. Updating their T&S after the fact does not change this. This can lead to jail time as it is often considered fraudulent.

The op has made it clear he will not send his personal documents to "scammers"

Changnow should return the coins to the same address but they insist on KYC.

Both parties should find a reputable third party to hold the coins, and is willing to verify the op's identity. The coins should be released after the op passes KYC and removes the FUD on changenow.

Changenow and every other exchange that requires KYC from customers must alert them about this before taking deposits..