I have a Physics undergraduate degree (MS in engineering, but I got that after working for a few years), and I now lead a team of firmware and software developers, so I understand what you are going through. Every manager is different, so it's tough to give general advice, bu here are three things that worked for me, or people I know.
First, if you haven't done so already, try looking at Craig's List, or other small job posting places. A lot of small companies that can't afford the big job sites post their jobs to Craig's List. Those jobs tend to have less people applying. The down side is that those companies generally can't pay as well, but it's easier to get a foot in the door. One of my Physics classmates found his first technical job on Craig's List several years ago.
Another thing you can do, if you haven't already, is try to work through contract agencies or what are sometimes called body shops (companies that work is outsourced to. You can often find them on Craig's List and the like). The smaller companies and the ones owned by offshore companies, seem especially not picky about whom they hire. Some of the agencies are pretty unscrupulous and greedy, so again, don't expect much in the way of pay or benefits if you don't have any bargaining leverage (i.e. no industry experience). It's pretty common for large companies like Microsoft to outsource large parts of their development effort to body shops, or just hire contractors through these agencies essentially en masse for things like software development in test, bug fixing, or software testing. I got my first job after finishing my Physics degree through a shady little contract agency. The pay was terrible, and there were no benefits, but after just six months, I was able to get enough experience to find a "real" job, so I quit.
The last thing is you can get qualified in some skill that isn't common. Everyone knows Python, Java, etc. so there are going to be lots of candidates for those jobs. A comparatively small number of people know things like LabVIEW, Smalltalk, FORTRAN, tcl, etc. Some of these technologies have certifications you can get. Both myself and a friend of mine with a Physics degree started out doing LabVIEW. I know another guy who didn't have a CS degree and started with Smalltalk, and one woman who started with FORTRAN. Look up a list of software languages by market share, or popularity, and go way down the list to find a language you want to learn. Then make sure there are companies with ads out for those languages, so you know the languages aren't totally dead. Find out which ones you might be able to get a certificate in either through industry, or a university extension program, or just teach yourself. I've had to hire people to program some of these not-so-popular languages. Some times we only get 1 candidate after weeks of searching. The down side is that you might have to relocate, since, obviously, not a lot of companies use these technologies. Once you get some industry experience you can likely move into more in-demand languages, so you don't have to base your whole career on writing COBOL. I mean, that language just has to go away eventually, doesn't it?
Sorry about the long post. I hope it was helpful. Good luck in your job search. I'm sure you'll find something.
~Lydia