no,seriously,wtf
bitcoin is supposed to be decentralised and anonymous
what you should do is go to any bitmixer service and just mix your coins
so no further questions asked by overzealous exchanges
have a look in the service discussion section,I would suggest bitmixer as the oldest and the most reliable one
Dear Anastasios you can try selling and buying bitcoins at btc-e or any similar exchange, usually most of the sites don't ask verification and if any exchange is asking for such proofs then either they intend to scam you or they want to know something which you should not share, like how you earned them.
And yeah please tell us which exchanges asks verifications so we can open them here at bitcointalk and save others.