The search engines and other sites aren't just building a profile of you based on IP. They leave ID cookies on your machine which are passed as part of the HTTP(S) request.
It doesn't matter how the data gets to Google/facebook etc, if the ID cookie is there, it knows who you are, and anything you then do over that connection will be added to the profile.
If you want to be completely unrecognisable you'd need to block or delete the cookie so the target website won't recognise you from the last time you visited, and use a VPN, and home HM Gov haven't got a warrant for the VPN company's logs.
If you only ever access the 'net via VPN, the only info the search engines etc will be missing will be your location... Although your search history, maps use and site visit history will probably give a good indication...