引っ越しに関する免許証の住所変更について質問です。今年中に引っ越しをする予定

引っ越しに関する免許証の住所変更について質問です。
今年中に引っ越しをする予定があるのですが、
今住んでいるところから車で5時間ほどの市が変わる引っ越しになります。
新しい家は
社宅で、
公共料金は主人の名前での契約にする予定です。
免許更新の時は、住民票で免許の住所変更をできるとおもうのですが、
更新ではなく引っ越した時の住所変更は住民票では受け付けてくれず、
公共料金の請求書などではなければ出来ないと、以前引っ越しの際に警察署で言われました。
その時は結婚もしておらず、
公共料金の請求書が来てから住所変更したのですが、
今回は、公共料金の名前は旦那なので、どうやって免許証の住所変更をすれば良いのでしょうか？？補足北海道です。

一体どこの都道府県の話ですか？。
住所変更の書類で「住民票はダメ」なんて、役所が発行する書類なのだから、信憑性は一番高いので、それがダメとは普通は考えられません。
その住民票に不備が有った（「本籍地が書いていない」「古すぎた」）だけではないのですか？
自分は、免許証の住所変更した際には、「更新無しでも、住民票を提出して」警察署でやりましたが

私の最近の過去回答読んでくれ。２～３日前に誰かに書いたよ。

警察署ではなく、免許センターで住所変更してください。
免許センターなら住民票でも住所変更できます。
まぁ、住民票取るのも費用がかかるので、公共料金の請求書や健康保険証などで済むならそれて良いと思います。
都道府県で若干の違いがあるので詳細は免許センターなどに問い合わせた方が確実ですね。

住所には二種類あります
本籍と住所
本籍は住民票に記載されている住所で、住所変更には住民票がいります
住所は現在実際に住んでいる住所で、住所変更には何も必要ありません

保険証はダメですか？
僕は何も提出せずに新しい住所を紙に書いただけで免許の裏に新しい住所の判子を押してくれましたけど…。
保険証だしたかな…。
ただ、住所変更した時に証明出来るモノは僕は保険証しか持ち合わせてなかったので、出したとしても保険証を出してますよ。