Yes, it is conceivable that targeted ads are based on IP address, which no non-rerouting client program can change. (Try Tor and see what happens.) Very determined ad sites might also be using browser properties, like installed fonts and screen resolution (among others) to identify a client.
Of course, if you explicitly sign into any service in private browsing, it will know who you are and probably apply targeted ads.