prior to の後ろは名詞しか置けないはずだと思ってる → 名詞しかではなく、名詞類(名詞、代名詞、動名詞)を置くことができます。
becoming Americanがthat territoryを修飾してるってことなんですかね?
→ 修飾していません。that territory が becoming(動名詞) の意味上の主語になっていると考えます。
just prior to that territory becoming American 直訳:その地域がアメリカになることになる直前に
Their community(S) relocated(V) (to French Louisiana)(M) just prior to that territory becoming(動名詞) American.
彼らの地域社会は、その地域がアメリカになる直前にフランス領のルイジアナに移転した。
参考にしてください。