You can find cheap accommodations at onsen ryokan, or Japanese style hot spring inns, if you can find one that will allow you to reserve without meal service. In most cases, people go to onsen with the expectation of an elaborate meal, but there are less extravagant ones and some that offer at least a portion of their rooms without meal service.
However, sento don't generally do this. A hot spring will offer a public bath (usually with water from the hot spring), and many of them are attached to ryokan.
In general, a minshuku or pension will be the most cost-effective option for a budget traveler beyond the hostel/backpacker mode. Many minshuku or pensions have no English-speaking staff, however.
I've stayed in a small number of basic ryokan that offered shared baths for cheap, even in Tokyo, but "cheap" in this case was $45-80/night.