Sería divertido movernos por Japón los cuatro juntos, aunque fuera por pocos días, sería muy freak!

Sobre Shikoku, si que sé algunas cosas, llevo tiempo informándome, pero no he estado, así que la info que te pase es la misma que la que puedas conseguir tu. Kyushu si, me lo conozco bastante bien, si quieres alguna información detallada pregunta.
Sobre el tema ir sin reservar alojamiento, como sabéis yo no suelo recomendarlo, básicamente porque:
-si vas en primavera probablemente te quedes sin el alojamiento que prefieras, si esta todo lleno te queda solo o lo super cutre o lo super caro, en ese caso siempre recomiendo tener todo atado, especialmente para la golden week. Octubre no es un mes que de problemas, yo en 2 meses (setiembre y octubre) solo tuve problemas 1 día, porque era festivo (tercer lunes de setiembre si no recuerdo mal)
-la mayoría de gente no tiene mucha idea de japones o inglés lo que les tira para atrás a la hora de liarse a reservar en persona
-a muchos os da mucho miedo ir sin tener nada reservado, la seguridad es relativa, depende de lo al límite que te guste vivir

-muchos queréis ir a un sitio concreto por motivos x (a mi me da igual estar en un pedazo de ryokan o en uno de cutre, de hecho los cutres me molan más, son más auténticos y son 100 veces mejores que un hotel occidental)
-la mayoría de la gente va entre 10 y 15 días a lo sumo, así que en ese caso si veo un poco pérdida de tiempo el ponerse a reservar
Yo me curo en salud pero la verdad es que no hay para tanto, reservar allí es casi igual que hacerlo en España, es decir, sin saber realmente como es el sitio, de hecho es más cómodo y rápido que hacerlo desde España, sobretodo si reservas desde el WIRC, donde recibes más y mejor información que desde aquí.
La clave claramente es el WIRC (welcome inn reservation center) una organización hija del ITCJ (international tourism center of Japan) que a su vez es hermana del JNTO (Japan national tourism organization).
Hay estas oficinas:
http://www.itcj.jp/eng/access.html , yo recomiendo la de Kyoto, es la mas fácil de encontrar, esta en el medio de Japón y te atienden especialmente bien.
Allí la persona que te atiende te orienta mejor, enseñándote los alojamientos disponibles (tienen una lista inmensa) dependiendo de tus preferencias (localización, precio, estilo de habitaciones, etc), y una vez escoges te hace la reserva por ti, y te imprimen un mapa y te indican como llegar de mil maneras, mejor imposible.
Es posible que pierdas algo de tiempo, pero a mi me gusta bastante el tema de hablar con japos, especialmente gente de cara al público, es todo un mundo. No lo considero tiempo perdido, además es algo que puedes finiquitar en 10 minutos o menos, especialmente si usas bases de 3 o 4 días en vez de dormir cada día en un sitio diferente.
Como eres tu Rafol te pongo un ejemplo de lo que hice en 2008, quizá se entienda mejor:
Llegué a Japón, a Nagoya, mi colega estaba por allí cerca estudiando, había acabado el curso dos días atrás, hacía días que no hablábamos porque había estado muy liado currando, ya habíamos acordado como nos encontraríamos, pero no que haríamos una vez estuviéramos juntos.
Nos encontramos, y hablándolo así rápido decidimos pasar de quedarnos ese día en Nagoya (ya la habíamos visto) e ir a Kyoto, para recordar viejos tiempos.
Durante el trayecto le comento mis planes, que eran estar varios días por Kyoto y alrededores hasta que al activar el JRP de 21 días nos valiera para el último día, o por contra movernos ya y los últimos días no tener JRP y pasarlos cerca de Kyoto o Nagoya.
Decidimos esperar esos días y despues bajar a Kyushu. Así que al llegar reservamos 6 noches en Kyoto (para los días de Kyoto, Ise, Toba y Amano Hashidate), 3 noches para Fukuoka (Fukuoka, Nagasaki y Yanagawa) y 2 para Beppu, a sabiendas de que podíamos ir al monte Aso y volver en un día (gracias a una japa de Kyushu que me encontré en el avión), los demás días eran una incógnita, por ser muy lejanos y porque en medio estaba Takachiho, que no sabíamos si iríamos pues había leído que ir eran mas de 5 horas de bus (info mala pues era yendo por el oeste, por el este son 3 horas).
Pasan los días, y una vez llegamos al día de Fukuoka preguntamos por Takachiho, nos aclaran la ruta, pero no el alojamiento, pues no hay oficina allí. Fuimos a Takachiho sin tener nada reservado, y en 2 minutos de estar en la oficina de turismo ya teniamos una furgoneta que nos iba a buscar a la estación de buses para llevarnos al youth hostel, una de las mejores experiencias que he tenido jamás.
De allí salimos a Kagoshima, buscamos un alojamiento para Kagoshima el día del monte Aso, pero sin reservar, nos plantamos en el sitio y el hombre nos dice que está lleno y nos lleva en persona hasta la puerta de otro ryokan cercano, flipante, nos condujo a la competencia
De Kagoshima salimos a Kyoto, pues no teníamos noche, y no sabíamos ni donde dormiríamos si en Kyoto, Osaka, o Tokyo. Como al día siguiente era festivo (cosa que no sabíamos, no se muy bien porque

) pues estaba todo lleno en Kyoto y Osaka, por lo que reservamos en Tokyo, llegando bastante tarde (fue el único problema que he tenido nunca), aunque el resultado es el mismo, teníamos que ir a Tokyo para ver la ciudad y alrededores e ir a Hakone y Sendai, solo que queríamos dormir en Kyoto por lo de no estar todo el día en el tren.
Las noches siguientes las pillamos en Sendai, porque en el tiempo decían que se aproximaba un tifón.
Fuimos a Sendai, pasamos 3 días y al volver a Tokyo reservamos en la oficina de allí (está un poco más escondida) para los días que quedaban pues ya sabíamos que iríamos primero a Hakone y dejaríamos Tokyo para el final.
Quizá un fallo que hicimos fue no reservar la última noche en Nagoya, aunque cerca de la estación está plagado de sitios cutres para dormir, y solo lo necesitábamos para dormir pues íbamos a estar el último día por Kyoto comprando gracias a tener JRP hasta el último día.
Joder vaya tocho.. hacía mucho que no hablaba tanto de mis viajes haha