When we talk about leveling a bed, we are not talking about making it perfectly horizontal. The idea is to make the distance from the print head to the bed exactly the same at all points on the bed. The whole thing could be tipped 30 degrees and it still would be "level" in printing terms.
When you level, you have a piece of glass on the printer. If it's to thin or a really cheap piece of glass it will not be flat. That is going to make leveling the bed impossible. You need a better / thicker piece of glass in that case. If you have some sort of aluminum bed and it's bent, that's a different issue, but you need to fix it just the same.
