If you guys don't mind small apartments and want to save money, I think you should use this site:
https://www.couchsurfing.org. You might be able to find Japanese people who are willing to let you stay for free.
Finding a cheap apartment to live in a short time is not easy if you can't speak Japanese. Renting an apartment requires you to sign contracts, have a guarantor, etc. I also have two friends from Italy who went to Japan for a month last year, but I never had a chance to ask them where they stayed during that whole month. They traveled a lot, not just to Tokyo and Kyoto but many other places as well, so I think they must haved stayed at a hotel or motel.