I'd also say reserving seat as early as possible is the best way - who really wants to stand on a train for hours on end?
About the planned schedule though, once you get past the busy areas like Tokyo and Kansai, you will find far more seats open.
Kyushu has some great sights too that few go and see. Nagasaki is the most interesting city on the island and worth a couple of days. Kagoshima could fill up a whole day nicely too - Sakurajima is wonderful, plus the Senganen Garden is superb. Beppu is famous for its hot springs, but its Hells Tour, plus monkey park/aquarium are all terrific.
For Fukuoka, there are many open parks, shopping, seaside historical areas, and urban neon. See this site as a good guide.
For Fukuoka, don't miss the Nanzoin Temple which is one of Japan's finest yet almost totally unknown to the outside world and completely FREE!
Look into a Fukuoka Tourist City Pass also.