4 Week trip Osaka - Fukuoka

Hi there,
I am planning a trip for 2 in November of this year for approximately 4 weeks.
We are looking to travel around the Kansai area, and spend time in Osaka (flying into Osaka), Kyoto, Nara, Mt Koya, etc, but also head down to Kyushu for the Sumo (and we are flying out of Fukuoka) . I'm wondering if anyone has any suggestions in regards to reasonable times to spend in each city and also things we should do and see. Specifically, we would like to stay in a temple on Koya, see Fushimi Inari shrine, and other temples in Kyoto. We're big foodies and enjoy getting off the beaten track into the countryside, I enjoy craft and sewing, so any suggestions along those lines would be amazing.
We would also love to visit an onsen at some stage, but my partner has tattoos and I understand that's still a bit of a no-no, so any advice on that would be great as well.

Truly the sky is the limit as to what you can see. You could spend 3 full weeks in Kyoto and still not see all that there is.
A lot of time your time should be spent in the Kansai area though since there is so much, and there are many regional passes to help you.
See:
http://www.japan-guide.com/e/e2357.html
for some examples.
A lot depends on what you want to see/do. Osaka is a great place for food. See www.bento.com for some ideas. Kyoto has its food too, but often more expensive.
There are many places worth visiting between your 2 end points. Some are:
Himeji (best castle in Japan),
Miyama for a tastle of old Japan:
http://www.japan-guide.com/e/e3985.html
Okayama has its castle, Korakuen and Handayama Gardens:
https://www.youtube.com/watch?v=5zAI3_N7NEM
https://www.youtube.com/watch?v=JGQ8o7k9GbA
Kotohira in Kagawa makes a great side trip and a magnificent half day hike:
https://www.youtube.com/watch?v=ley9rVIewoQ
Kurashiki is a nice quaint place to see its old canals.
Hiroshima and Miyajima are must see places along the way.
Onomichi is a off the beaten track place with its temple trail, as well as Konsanji, a mix of a Buddhist temple and Disneyland:
https://www.youtube.com/watch?v=97Q5EjEOXI8
Iwakuni with its iconic bridge and mountaintop castle are wonderful to see (and not overrun either):
https://www.youtube.com/watch?v=0COOZXi66mM
The Akiyoshido Cave and Akiyoshidai plain are magnificent and often overlooked gems in Yamaguchi.
Shimonoseki has a number of scenic sights as well, and is often ignored by the tourist books and guides.
Kitakyushu has a nice castle, Kokura, plus its old style Moji Retro area, and Sarakurayama is one of Japan's finest mountaintop views of the city (and totally empty of the tourist hordes!):
https://www.youtube.com/watch?v=Hl1pCW9Ibbk
Finally, Fukuoka is famous for its ramen and spiced cod roe (mentaiko), but also one of Japan's finest temples - Nanzoin - awaits you and is nearly unknown to the world:
https://www.youtube.com/watch?v=lT4VQFmHFyM
There is a good guide to the city's best sights on:
http://www.thejapanfaq.com/fukpic.html
and more previews at:
https://www.youtube.com/playlist?list=PL7LcPcmoSg-j4RLa6iC7ayvBAbOn8-0...
Look into a Fukuoka Tourist City Pass while there:
http://yokanavi.com/access_tourist_eg