What is the smallest set of constants from which we could derive all the others?
There's a good essay about this by John Baez, "How Many Fundamental Constants Are There?". He counts continuous parameters of the standard model of particle physics (with massive neutrinos) plus general relativity, and comes up with 26. He doesn't count the strong CP angle on the grounds that the measured value is consistent with zero; I think it should be counted, because it is a parameter of the theoretical model that we measure experimentally, so I would say there are 27 parameters. But I'll stick with 26 for this answer.
The essay also lists 26 specific parameters (masses, gauge coupling constants, and so on), but properly speaking those aren't the parameters of the theory. Saying that there are 26 parameters just means that the abstract parameter space of the theory is 26-dimensional. Listing specific parameters amounts to putting a particular coordinate chart on that space, and there's more than one way to do that.
Is it possible to make suitable adjustments to the other physical constants such that their values are different from what we observe now, but the behaviour of everything in the universe was unchanged?
With the 26 specific parameters in the essay, no.
However, we could use a larger number of values to parametrize the theory. For example, we could use the values of $c$, $\hbar$ and $G$ in arbitrary units that (unlike Planck units) don't set their values by definition, together with the 26 values from the essay in those units instead of Planck units. (Modern SI units aren't suitable for this. The old SI units that defined the meter and kilogram using artifacts in vaults, and the second as 1/86400 of a day, would work.)
These 29 values are projective/homogeneous coordinates for the 26-dimensional physical parameter space of the theory. Values that differ only in a change of the arbitrary units project down to the same point in the physical parameter space.
There are other ways to expand the parameter space that have nothing to do with what are generally called units. For example, there's a large freedom in the definition of the fermion fields that we use to diagonalize various matrices, mostly Yukawa coupling matrices. You could instead leave those matrices in general form; that would give you dozens of additional parameters, many combinations of which would map to the same physical theory after you re-diagonalized the matrices.