こんなふうに一括置換して、
% find . -type f -name '*.sh' -print0|xargs -0 perl -i.org -0777 -pe 's/(\s*#![\w\s\/]+\/bash)/$1\nexport LANG=C\n/'
シェバンを表す正規表現に「\s」を含んでいるのはわざとです。
こんなふうに確認すればいいかな。
% find . -type f -name '*.sh'|while read FILE do echo ${FILE}:$(diff ${FILE} ${FILE}.org) done ./hoge.sh: ./hoge2.sh:2,3d1 < export LANG=C < ./hoge3.sh: