I would greatly favor the spellings Alison or Allison over Allyson, but between the four names you've listed that would be my pick. I don't like Katelyn or Kaylin particularly, and Natalie has always sounded really prissy and spoiled to me.
I think Alex and Allyson (or whatever variant) would be fine together as long as they didn't have nicknames that were any more similar like Ally and Allie or Al and Alli, know what I mean?
www.qwantz.com