携帯番号交換しとくんだったな。。。
The sentence means "We have interchanged phone numbers in advance." This makes no sense with the story unless I add "should" before the "have". So could ~teoku's meaning also include "should" ("should prepare in advance") in casual speech, or something like that, which could have this sentence make more sense for me?
You are correct.
「[携帯番号交換]{けいたいばんごうこうかん}しとくんだったな。。。」
means that the persons involved DID NOT exchange cellphone numbers.
「しとくんだったな」＝「しておくんだったな」 = "should have ~~ed"
「～～しておくんだった」, which is used idiomatically, expresses one's retrospective regret of not having done ~~. In this sense, one could call it "invisible" as it is all idiomatic instead of any part of the phrase literally meaning "should".
The "visible-'should'" versions are:
「～～しとくべきだった」 and 「～～しておくべきだった」
Thus, the sentence in question means:
"We/You/They should have exchanged cellphone numbers."
