携帯番号交換しとくんだったな。。。 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".
Thus, the sentence in question means:
"We/You/They should have exchanged cellphone numbers."