It might be quicker to list the places you can not buy mobile phones in Japan.
All of the places you mention, and more, have them.
Convenience stores usually carry the prepaid models, for example. Practically any electronics shop has them. Many car specialty shops have them. I've seen a mobile phone corner in a combination video rental and bookstore place. The strangest place I have seen them is at a forklift dealer.