If you're running into these problems for jobs that do list PhD as the minimum requirement, you should consider it a strong signal that avoiding working there is a net positive for you.
And if you think you have it rough, try getting jobs after having dropped out of a PhD program a few years into it. For some reason, at least in the sphere of my friends and associates, this signals "quitter" and "not as smart as a PhD person". I've interviewed such candidates and I'd say it's a mixed bag with respect to whether I've preferred them over PhD candidates I've interviewed for jobs, but almost uniformly I've had one or more colleagues raise the question of said candidates' ability and determination.
People (employers and PhD holders alike, really) need to understand that having a PhD is a strong signal for exactly three things, in this order: a person's willingness and ability to tolerate a certain kind of experience in the very narrow context of academia, some minimum level of expertise in the field above the typical undergraduate degree holder, and some further expertise in a very narrow slice of the field above a typical Master's degree holder.
How would you explain the several year gap in history without mentioning the PhD program?
To specifically counteract the "can't code" item, have plenty of practical items on your resume; include your published papers and conference presentations, but also include projects you've contributed to and similar. (For people doing a PhD who plan to work in industry, make sure you present at some industry conferences, not just academic conferences, and publish your code as/into Open Source projects.) A CV for an academic position doesn't work unmodified as a professional resume (with possible exceptions if you want to work in an industry research lab).
In the specific context of CS, if you look at medium to large companies, you should already ask questions about the technical job ladder (such as making sure that one exists, rather than the only promotion path leading into management). Ask specific questions about how a PhD affects your starting position on that ladder. If it doesn't at all, then seriously consider looking for somewhere that it does. A company that values PhDs seems less likely to hold the misconceptions you mentioned.
In data science which is the track I'm on, I've run into situations during interviews where
1) I can only scratch the surface of what's being asked
2) I answer the question to the satisfaction of the interviewer's skill level
3) I answer the question beyond the interviewer's skill level.
Only #2 is good. #3 happens rarely but you'd be surprised at how often it happens even at top5 companies. I've been dinged from interviewers in the #3 camp who were looking for the simpler answers. #1 is always a learning experience for me :)
