PCに直接接続されているモニター上のコンソール（以後tty）は、基本的に日本語表示に対応しておらず、OSのロケールを日本向けに設定すると文字化けに悩まされること必至です。
そこでいくつか対策を考えてみました。

その場しのぎ

export LANG="C"`

とコマンド打って環境変数LANGを変更すれば、とりあえずは英語出力となり、最小限の対応はできるようになります。
(なおLANG=C は既定値を使うという意味で、英語にするという意味ではないので念の為。）

tty使用時のみ文字化け回避

ttyからログインされた場合のみ環境変数LANGを変更するようにして、
tty上では文字化けを回避、ssh接続時は日本語出力されるように出来ました。

~/.bashrc

# 末尾に追加
# ttyコマンドの出力に"tty"が含まれていた場合`export LANG="C"`を実行する
(tty|fgrep -q 'tty') && export LANG="C"

※全ユーザーを対象とする場合は/etc/bash.bashrc(debian系) /etc/bashrc(redhad系)を修正。

tty自体を日本語表示に対応させる→放棄

理想なんですが、以下の理由により諦めました。

日本語表示対応のターミナルエミュレータを、怪しい方法で稼働させることで対応できるようだが、その怪しい方法自体にセキュリティ上の問題がある。
日本語フォントも入れなければならない。
そもそもttyを使う機会が少ない（ワークステーション用途ならX入れるだろうし、サーバー用途ならssh使うだろうし）

どうしてもというなら、fbtermで検索してみてください。

言語の既定値自体を変える→放棄

localectl コマンドや、ディストリビューション付属の設定ツール(Raspianならraspi-configとか）を使用してロケール自体を文字化けしない言語に変える方法。
この方法だと確実に解決出来ますが・・・日本語表示を諦めるということなんで、
sshやtelnet経由でも常に英語出力とかになってしまいます。
sshであればターミナル側のフォントを利用して日本語表示を行えるため、ロケールまでいじるのはちょっと大げさな気が...

参考文献

ttyとかptsとかについて確認してみる