Sadly they actually can. Apparently smoking isn't deemed one of those things that are "protected". Infact if you claim to be a non smoker and the company discovers you're a smoker, they can infact dismiss you for it!
Religion is protected against discrimination, that's why Christian companies cant do that.
Have you gathered feedback? You may be doing something glaringly wrong to other people but not to yourself.
A common thing for me with external candidates is the appearance of desperation. Some people will attempt to show willing, when they just plain come across desperate for anything someone will throw to them. But it may not be apparent to them.
Give them something to think about, make them remember you. As silly as it sounds, if you ever get asked about your biggest achievement, or something you do outside of work, make it really stand out in their mind, it might be bullshit, but as long as you can sell it, you're good.....someone who says they enjoy programming or playing video games won't stand out in your mind as much as someone who says they ride giant pink elephants at the weekend (a little far fetched, but you'll get the idea) If I interview half a dozen people in a day, people start to blur together sometimes, so having that extra something that makes you stand out WILL help make you memorable.
Research the companies, keep a note of what you've applied for and with who, people who just fire off CV's everywhere don't tend to do this and are very unprepared when an employer reaches out to them. My recruitment Manager makes countless calls to people who's response is along the lines of "what job was this for?" On the note of applying for jobs - blag! If you see a few things you feel you might not be able to do, still apply. Have a quick google, play with the product/service they're asking about, just enough so you can talk about it (or know about the terminology they mention) The job description is for the ideal candidate......... you rarely find the perfect person who knows everything you've asked for.
You honestly do not need qualifications, and sadly rejection is always a part of the recruitment process. I can get 15-20 applications for a single role sometimes, so 19 people I have to say no to (well thankfully I don't, the recruitment team do it for me!) Other times I might only get 2-3 people for the same role. You just need a little bit of luck sometimes.
A little bit of knowledge on different operating systems will go a long way to helping you. Install Linux in virtualbox on your PC - without the gui. Get used to navigating around, install software like mysql / apache etc play around with the configs, break them, fix them. Having even a small amount of knowledge of Linux will likely give you a huge advantage over other people, it's massively used in businesses and most people are afraid of it.
- Have a look at the LPIC-1 learning material on here if you want to improve your skills.