Well don't you still need a phone to dial skytel number to page somebody? You did mention different cities so maybe the pager idea will work. But if two cities are on the same phone network...

There is no right answer for communication solution. You can try talking her into a ham radio like a vx-2r from yaesu and ham experts here will give you pointers on how to go about it. Keep the cellphones, maybe invest in walkie talkies.