ホームレス状態です（住民票抹消・保険証なし・身分証明書なし）

すでに回答がありますが、居住実態がない場合、行政は職権により住民登録を抹消することが出来ますので適法行為です。
あまり知られていないことかもしれませんが行政では職権消除は一般的事務のひとつです。
さて住民登録の復活ですが基本的にはANo.2・3で間違いありません。
ただし、職権消除から５年以内なら最終住民登録地に申請されれば「転出証明に準ずる証明書」を発行してくれます。
こちらの方が戸籍や付票よりも転入手続きが若干スムーズです。
最終住民登録地に行けないようであれば、戸籍や付票を現在の居住地の役所に持っていき転入届をすれば大丈夫です。
過料については行政判断なので悪意がないと判断されればかけられないかもしれませんし、単純判断でかけられるかもしれません。

ANo.2　の補足です。
住民票の回復の手続きは、転入届の手続きと同じ感じです。
住民票削除の証明＝転出証明書の代わりになるんだと思います。
なので、回復の手続きと言っても普通に転出証明書代わりの削除証明書
と転入届と戸籍謄本（全部事項証明）と戸籍の附票謄本（全部の写し）を持って戸籍住民課、各市民課へ行き普通に転入手続きで済むと思います。

あと、身分証がない場合のキャッシュカード提示については
友人の経験上の話ですが、住基カードを発行する際、身分証の提示を求められたそうで
仕事を辞めた後で保険証やパスポート・免許書も無かった為（そのため、住基カードを作る事にしたらしいのですが）
受付の方に、その旨を正直に話した所、本人名義のキャッシュカードの提出と口頭での質問（生年月日や前の住所、両親の名前など）でOKでした。
カードは、2枚ほど提出を求められる場合があると思いますので
あるだけ持っていかれたほうがいいかと思います。
また、最後に置いてた住民票と同じ住所が記載されている
通帳などがあれば、一緒に持参した方がいいかもしれません。
もし、それでもダメな場合は職員の方が色々と考えてくださると思います。

無事、住民票が回復できて住民登録が済んだら、ついでに役所でそのまま住民基本台帳カード（顔写真付き500円）も発行しておいたほうがいいかと思います。
身分証の代わりにもなりますし、有効期限も10年ですので今後また何かあった時に役立つかと思います。

もう一つ、住民票を移動しなかった罰の件ですが
転出届を出した後、転入届を出さずにどこにも住民登録をせず放置していた場合は罰金が取られるようです。
職権で削除された場合は、住民票を移動せず＝転出届は出さずにそのまま置いていてたので罰金は無いのではないでしょうか？

現在住んでいる区でしょう。
住民票自体、抹消することができるのか、疑問です。以前住んでいた区役所の方が問題なのでは。
その区役所で、事情があって、ホームレス状態で、住民票が移せなかった事情を話したらどうでしょう。
それから、年金や国民保険料の滞納についても相談しましょう。
区役所の職員は公務員です。相談に乗る義務があります。