基本的には「出来ません」

合法的には。そう考えられたほうが良いと思います。

どこの国でも当然ですが自国民の雇用を第一に考えます。
誰でも出来るような単純労働は基本的にはできません。

「外国人でも誰でも自由に働いて良いですよ」という国はちょっとおもつきません(あるかもしれませんが)。

もちろん、政府がくまなくチェック出来ていない国も多いですから、「アルバイトをしながらヒッチハイクをして旅を・・」ということも出来てしまうかもしれませんが、あくまでもそれは「違法」である可能性が高いと言うことです。

もし出来たとしても・・・仕事を見つけるまでの時間、どんな仕事か分からないリスクの高さ、現地の給与水準を考えたら、日本でお金をためてから旅に出るほうがよっぽど賢明です。

ファーストフード店などの単純労働で1000円近くの時給がもらえる国なんて普通ないですよ。日本なら日給で1万以上稼ぐ仕事も比較的簡単に見つかるでしょうが、中国じゃ地方都市の月給レベルですから。