So I've since been and returned on my trip to Japan, and had an amazing time cycling around the country-side - I genuinely cannot imagine a better way to explore and get to know a country than by bike. In the end I took my own bike, but I still visited bike stores, and paid some attention to what was available.
I'll preface this by saying, my Japanese is almost non-existent. Nearly all of the places I found were from Google Maps because they had listings with enough English to know they were a bike shop.
When I arrived in Osaka I visited several bike shops to find supplies for my journey. These were in the "city grid" area mostly to the west of Dotonbori. These tended to be hipster-ish type establishments selling fashionable bikes like fixies etc. especially around Amerika-mura. Bikes here seemed to be a comparable price to Australia, around the 8000 yen mark give or take (I didn't take notes, so I'm just giving a rough range). There was also at least one high-end bike store that I saw, but didn't enter. Bikes here would have been seriously expensive.
Some large department stores also have a bike section. Bic Camera definitely did on the ground floor, and they had a pretty wide range, so there would be something there to suit a long journey, but places like Don Quijote and Tokyo Hands have nothing.
I also came across some bike shops in Denden town, but these seemed to be small hole-in-the-wall establishments that were predominantly bike mechanics who focused on repairing the ubiquitous mamachari. The one that I did approach, the owner just waved me away (he probably spoke no English).
Before I went, I researched buying second-hand bikes, and it doesn't seem to be something easy to do, even if you can speak Japanese. Some places will repair old bikes and sell them, but the places I found out about only opened for sale on set days, around once a month. Then on top of that, the bikes were mostly mamacharis. Buying second hand bikes from online classifieds is not an option unless you have strong Japanese reading skills.
An important point to note, Japan has compulsory bike registration program implemented to help prevent theft. All bikes sold through a retailer will be registered through the police. You have to pay a small fee (~400 yen I think) and get a registration sticker. The retailer should do all of this for you, but I believe you have to provide an address. All bikes are supposed to be registered by law, but there is no penalty if they aren't (I never registered mine, and I never had any trouble).
As for large bikes, I didn't try any because I wasn't going to buy, but from eye, the bikes I saw in stores were generally at least one size too small for someone my size.
Long story short, buying a bike is definitely possible, but from my experience you'll probably end up paying a premium (at least in Osaka) and that's if the store has something large. Cycling is very common, but that demand is almost entirely taken up by mamacharis. Other kinds of bike seemed to be more of a specialty. By far the best option for tall people is to take your own bike, especially if you are trying to stick to a tight budget.
