Many small hotels (self-described as minshuku or ryokan) are not bookable through the Internet. Such hotels often have availability even long after all of the Internet-bookable options have sold out.
Booking is made by phone. Obviously, this require knowing some Japanese, as very few have English-speaking staff.
The main difficulty is to find these small hotels that often have no Internet presence. Here is the best way I have found:
- Go to the Japanese yellow pages website: http://itp.ne.jp
- Type the name of the city you want to stay at
- In the left bar, choose
旅行宿泊 (tourism accommodation)
地図検索への切替 to switch to map mode
- Zoom to downtown, as some minshuku can be in very remote places far from public transportation
- You get a list of hotels in the desired area
- Open each hotel name in a search engine
- Filter out the hotels for which the search engine shows Jalan/etc (because you have already searched through these websites)
- The search results might have some blogs or pictures of the hotel, and price information
- Call the ones that seem OK. It might take 2 or 3 tries before you find one with availability.
As pointed out by Mazyod, another option is AirBnB, they might have different occupation patterns than usual forms of accommodation, because some people rent their place precisely while they go on vacation.
One other solution can be urban camping, which is tricky but feasible in Japan with a bit of attention. If travelling with a low-cost airline, remember that tents might not be allowed as cabine luggage.
A last resort is cited by Wikivoyage:
24-hour comic book library/internet cafes known as manga kisa, are common [...]. This is one of the cheapest ways to crash [...]. No bed, but you have a comfy chair and a PC and/or DVDs if you can't sleep. Later in the evening, karaoke boxes often offer discounted prices for the whole night, they usually have a couch you can sleep on. Most of these cyber cafes charge ¥1500–2500 for 8 hours.