Bad connection with the 3.5 jack

About all that's left to do would be to maybe try flushing it out with 90% or higher concentration isopropyl (rubbing) alcohol then blow it clean with a can of compressed air. If that fails then yeah, you're down to opening up the Shuffle and removing the logic board.

iPod Shuffle 4th Generation Logic Board Assembly Replacement - iFixit Repair Guide

Once the board is out, you might be able to see if there's something wrong with it. Unfortunately, I wasn't able to find any information on how to go about replacing the headphone jack so I'm afraid that's something you'd have to figure out for yourself. The part itself is readily available online but I can't tell just from pictures how it's attached to the logic board. You may have to solder it, or perhaps not. Here's an example of where you can buy the part; there are many more online.

Headphone Audio Jack Hold Switch Module Repair Part for iPod 4th Gen. iPod Color Photo 20GB 30GB 40GB 60GB - AliExpress

If you decide to tackle the replacement, be sure to take lots of pictures, then you can use them to author your own guide and help out the iFixit community, who will appreciate it.