You could get a PO Box, and a voip type phone number from a free provider (I'm not too familiar myself with any but I'm sure there are some), that way you don't need to give your real address or phone number to the registrar. Keep in mind that the PO Box will be linked to you so if you did anything illegal with the domain it could be traced, but if you just want to stop people from tracking through whois then that works. Whois privacy is a good idea too but there are situations where it won't work, such as the few moments before it is active. Some sites like whois.sc keep a history of whois records and people can pay to see it. So if your site's whois privacy expires, or you forgot to turn it on right away etc... it's on there.
For the web host part, it's kinda hard as you will need to give them a credit card number, but I think prepaid credit cards, like those vanilla gift cards, might work. So you could buy one at the store using cash and use that to sign up for the host.
You will need an email address at some point throughout the process but you can use a throw away gmail, and once the site/server is setup, switch the email to one hosted on that server. Keep in mind however that if you need to do anything that involves the domain, like transfering to a diffrent registrar, if the email is tied to that domain you want to make sure the domain will continue to resolve to your DNS server during that whole process and that your host also works. For example if you need to receive any type of email confirmations.