I change my IP, and then I want to access a website with a new identity I also need to delete the cookies. Would that be enough? Are there any other ways to store information and get it back with the next request?
Use the Tor browser.
This site explains how browsers can be tracked, and has a feature to test if your browser is vulnerable.
Along with 0x40's suggestion to use the TOR browser, I would recommend looking into booting to a secure OS such as tails. Tails uses the TOR network for all of your networking, preventing other avenues of attack.