[lambdatronics]

>What would it even mean for a particle to have an "action" (whatever that is) that is not minimized?

The particle doesn't have an action. The trajectory of a particle is what the action is defined in terms of. One way to think of it would be "it's a measure of how much the trajectory deviates from the one dictated by Newton's equations." Pretty much like what you said: "I can always find a measure that something else is always a minimum of."

About what a trajectory with non-minimal action would look like: it would be an arbitrary violation of the equations of motion for the system (ex: free particle moving in a zigzag instead of a straight line at constant velocity). Moving in a straight line at constant velocity is what Newtonian mechanics prescribes, and that trajectory will minimize action for the corresponding Hamiltonian.