[Sangetsu]

I usually go to QB House, which is a barber shop chain with many stores in metro Tokyo. They can be found near (or in) larger train stations and shopping centers. They charge only 1000 yen for a hair cut, and in my experience, they do a better job than the much more expensive, high-end salons.

At QB House you simply put a 1000 yen note into a machine, which then gives you a ticket. You present the ticket to the barber when your turn comes up. The machine doesn't make change, so make sure you have a 1000 yen note before you go in.