1. How do you delete the contacts ?? like permanently deleted them ?
2. If I clear all the history and book marks and all that, is there still a way to find out what websites I have been visiting ?
I think the best way is to factory reset the phone and should be done, wiped clean. No risks. just like the name implies: back to stock.
3. After deleting the messages and calls history, is there a way to retrieve them - like are those details being stored somewhere ?
If you wanna back it up for personal reasons, you can get some app to back it up. However if you are just worried about it being recoverable then factory reset is best, just reset and cleaned to stock.
I'm with android all this while, so cannot guide you from here, however a quick search came out with this:
http://www.digitaltrends.com/mobile/...set-an-iphone/
Hope that helps, pls ask if u require anything else, cheers.