"all over the country"
"all over the nation"
最もわかりやすいのはこのように"all over"という「~中をめぐって」を意味する表現を用いることですね。後半の部分を変えれば、特定の国や、もしくは地域を指定することも出来ます。
次によく使うのは例二つ目ですが、これは実は興味深い国土の違いにより日本で用いる場合には伝わりづらいかもしれません。なにせこの表現は直訳すると「海岸から海岸まで」であり、東西に長い国土が前提となっているからです。実際にアメリカでは国中を旅する、というと自然に浮かぶのが大陸横断という発想です。しかし日本の細長い国土ではどうでしょうか。あまりピンと来ないかもしれませんね。
最後三つ目の表現ですが、あまり日常的なものではありません。しかし特徴的な言い回しですので、少ししゃれた言い方をしたいときに役に立つかもしれません。ただ、本当につつがなく全国を飛び回るニュアンスですので気を付けてください。