Strange as it may seem, many folks not in a raiding team have yet to see LK down. On the servers I play on LK pugs are rare, at best they usually get to Blood Queen or Sindy.
I'm not part of a raiding team (though my guild raiding team have had LK heroic on farm for a while now). Doing ICC once a week at most with the other non-raiding members and alts, and often with a few randoms thrown in, I've yet to see LK down, though I'm feeling confident about this weekends run.
I still think out of the general playerbase, and certainly on the realms I play, there are more people who don't have Kingslayer than those who do. So even now killing LK is something that should give some semblence of satisfaction.