When I try to solve a hard problem, I have no idea on what to do before I write anything on the paper: apparently, only after I spent hours on a particular problem I find the key idea by just a coincidence. This makes me feel that training myself by solving tons of hard problems on integration or geometry etc... is a waste of time since for the most of it I randomly run into the solution by coincidence and that is what I mean by randomness when solving a math problem.
So my question is:
how to overcome that? Should I try to solve each problem on my head without writing down any thing? Or what do you advise me to do? And is this a thing that I can solve or I am just not smart enough?
A lot of real mathematical research is about going down a lot of different paths hoping to find one that leads to a new insight. However, that is also backed up with developing a strong sense of which paths are more likely to lead to something useful. At least with homework problems you know that there actually is meant to be an answer, compared to a researcher who may spend years trying to prove a theorem that isn't actually true.
Solving a lot of problems of a similar nature is one of the things that helps build that understanding - the first time you use a Weierstrass substitution to calculate a gnarl integral it seems to come out of nowhere, but if you do it ten times then the next time you see a weird trigonometric integral you'll see the trick immediately. Similarly, it's good to make sure you have a solid grasp on fundamental concepts before you move on to more sophisticated things, because sometimes a problem falls just outside the usual methods and you need to work from first principles - for example, you might have a theorem that requires assumptions A, B and C, but if you're given a problem that satisfies A, B and D you'll need to go back to the proof of the theorem and check what the difference between C and D is on its application.
I also can't understate the value of taking pacing yourself, which is something that isn't covered as often as it should in my opinion. If you get stuck on a problem, then sometimes the best thing you can do is walk away and do something else. Your brain gets stuck in loops and breaking out of that loop increases your chance of figuring out the thing you've missed. (As apocryphal as the stories of Archimedes in the bathtub and Newton by the apple tree are, there's a grain of truth to them.)
The last thing I would point out is that if you find yourself stumbling on the right answer almost at random, that might be a sign that your brain is already wired right for mathematics. You can only have a "Eureka" moment if you're able to see the patterns in how things fit together, and so mathematics can often be a weird combination of heavy grinding and random inspiration.
(Also, remember that "It's always in the last place you look" is often true just because once you find it you stop looking. If there are ten ways you can approach the problem then sometimes you'll need to try all ten before you find the one that works, and sometimes you'll get it first go and that's just how it is.)