チャリメインにすれば、結構期間は短縮出来るはずですね。
今軽くググってみましたが、北海道一周25日でした人がいるみたいです。
ちなみに、通ったコースはhttp://murayann.hp.infoseek.co.jp/1996-07/1996-071.html
バトンの回るテンポが問題ですね。

要するに、海沿い一周に拘らなくても、各地のランナーが次の人に回せるところまで走って、
最終的に全都道府県走れればいいんじゃないかと。
ランナーの所在地でコースを決めながら、直線でまず北上、そして南下って感じですかね。逆でもいいんですけど。
ちなみに、8000キロの距離で日本一周した人は、約8000キロを80日で走りきってます。
毎日確実に次のランナーに繋げれば、この記録を抜くのは可能かと思いますが、
ただ、平日はどうしても次に回せない日が多くなりそうですから、実際はもっとかかるでしょうね。

時間の自由になる大学生層が沢山参加してくれれば・・。