Do filters work on a "per sample basis"?
Obviously, filters need more than one sample of input – I mean, a single sample is a single number, and how would a single number have something like a frequency? Filtering is something you apply to a digital signal, and signal is defined by being a changing entity – i.e. different samples.

Hence, digital filters always need sequences of samples. The typical (non-rate-changing) filter works in a matter that each time you "push in" a new sample, an output sample "pushes out" of the filter.

You should definitely brush up your knowledge on what a digital filter is, and especially how FIR filters work. The important point here is the understanding that application of a filter to a signal is a discrete convolution. 

You're absolutely free to change the system with which you convolve any time – but you'd break the time-invariance that makes LTI (linear, time invariant) systems such as FIRs so "easy" to handle.

EDIT: with your clarification: 

Yes, any FIR will need "history" of samples. But also, yes, you can recompute the coefficients anytime, and "switch over" to a different FIR. However, you must make sure your new FIR's "delay"/memory elements were already filled with the previous input samples, otherwise you'll get inconsistencies.