On a totally orthogonal axis: My biggest problem with tackling math problems early in life was psychological. My inner critic would say nasty things to me when I didn't get the answer right away, making it impossible to stick with exploring the problem. Once I overcame that, I got lots better at math.
And working on yet another axis, the most useful tip I've gotten on how to think about problems is to "think in extremes". Perhaps more applicable to physics than math, but a classic example is the puzzle where a ship in a lock (closed system/giant bathtub) has an engine break down. As the engine is being hauled out for repairs, the chain breaks and the engine drops into the lock beside the ship and falls to the bottom of the lock. Does the water in the lock rise, fall or stay the same? The only person I ever told the problem to that solved it described his technique: Imagine the engine is the size of a pea and weighs 20 tons. Shazaam: The water in the lock falls because it is now displacing its volume, instead of its weight in water.
I like to use extremes and the intermediate value theorem, ie if you have two extreme points, and some continuous curve connecting them, it passes through all the points in the middle. It's a good shortcut for "is it possible to balance X and Y" questions. Like is there a hexagon with 'equal' area and perimeter? It's easy to conceptualize ones on each side of the ratio, and you can smoothly deform between them so the ratio is continuous, hence there is such a hexagon.
Thinking in extremes helped me to understand the Monty Hall problem. Imagine there are a hundred doors instead of three and 98 wrong ones are eliminated. Should you switch?
If you don't mind, could you share how you overcame that? I think for me at least a lot of it is/was not being able to be comfortable struggling with a hard problem for an extended amount of time, probably due to being used to only solving fairly trivial exercises and thus feeling dumb/the problem feeling impossible if it wasn't clearly solvable under a short timeframe.
Mostly, talk therapy. As you say, struggling with a hard problem for an extended period of time and feeling dumb is part of the process. For me, the shame was excruciating, so I'd turn my attention to anything else to stop feeling shame. The shame was intense enough that the underlying "felt sense/thought" was "I don't deserve to be on this planet". With the help of a therapist, I managed to start looking at myself and _managing_ the shame, so I could then examine my behavior and experience: Oh, I said that mean thing to somebody - I (deservedly) feel bad and want to change how I treat people. Oh, I couldn't get a math problem right away: I don't need to feel negatively about myself because of that. Frustrated, sure, but NOT "I don't deserve to be on the planet". Shame that intense tends to be (and was for me) rooted in childhood: Weak/bad parenting. It's a project to overcome it.
And working on yet another axis, the most useful tip I've gotten on how to think about problems is to "think in extremes". Perhaps more applicable to physics than math, but a classic example is the puzzle where a ship in a lock (closed system/giant bathtub) has an engine break down. As the engine is being hauled out for repairs, the chain breaks and the engine drops into the lock beside the ship and falls to the bottom of the lock. Does the water in the lock rise, fall or stay the same? The only person I ever told the problem to that solved it described his technique: Imagine the engine is the size of a pea and weighs 20 tons. Shazaam: The water in the lock falls because it is now displacing its volume, instead of its weight in water.