thatの後ろって助動詞から始めなければ行けないとかいうルールはありますか？ →　ありません。必要に応じて使用します。
助動詞なしの例：Little did I dream that Ken comes from Osaka because he speaks without any trace of Kansai accent.
ケンが大阪出身とは夢にも思わなかった。と言うのは、彼には関西訛りが全然ないから。

wouldやcouldと過去形になっているのは、thatより前の文が過去形（did）になっているから時制を合わせなくては行けないためですか？
→　その通りです。「時制の一致」ですね。

参考にしてください。