If you're a celebrity organizing a world tour you are guaranteed to have dozens of crew members or partners resolving various issues with logistics in every country. Remember that visas aren't the only barrier - you need legal contracts, booked venues, insurance, transportation, backup plans if something goes wrong, advertising, security, accommodation, etc. And not only would the celebrity in question need a visa to travel, but also everyone else in the crew as they're essentially short term employees in a foreign country.
So the answer is yes, even big time celebrities need a visa (or an equivalent, such as an EU passport for EU countries) for every country where they perform. But no, that's not a big deal for them. And keep in mind that celebrities can be refused a visa as well, just like normal people:
British authorities denied rapper Snoop Dogg a visa for a series of planned concerts, publicists for his tour said in a statement Saturday.
A spokeswoman for the Home Office said she couldn't comment on an individual case, but did point out that foreign citizens could be barred from entering the country if there were concerns about their presence.