That sounds very like like a simple bad connection or dry joint to me.
It sounds like you have some decent fault-finding technique already but, if you've not already tried it, you could try disturbing it while it's on. Switch on and apply some signal and have a tap around with an INSULATING IMPLEMENT (like a plastic pen or a wooden stick). Obviously, keep your hands well away from all of the electronics while the device is plugged in, *even if* it is switched off. See if you can make the symptom better or worse.
Common failure points are input and output connections, volume and tone controls etc, and generally anything large and heavy soldered to a board.
Otherwise, yes, you might have to resort to tracing the signal though. This sort of fault could also be due to failing capacitors, diodes, ICs etc...
but it's always worth having a good look for the easy things first!