One short answer I could point you to regarding this question is a topic called "local interpolation" using a compactly defined Lagrange basis with a prescribed size (perhaps size 50) of the parameter space. I talk about this in the context of kernel-based finite difference methods in remark 19.8 of my book: some of the references I point to there are (http://epubs.siam.org/doi/abs/10.1137/090769570, Hangelbroek is an outstanding author) and (http://www.sciencedirect.com/science/article/pii/S0377042711...). I think it's also possible to look at this question from the framework of moving least squares/approximate approximation (http://link.springer.com/chapter/10.1007/978-3-642-56103-0_8) or maybe even quasi-interpolation, depending on how you think about it (http://link.springer.com/article/10.1007/BF01279020).
If you'd like to talk about this offline, email me (see the blog post). I'll still post any thoughts I have here.
> Notice that both the polynomial and kernel methods have less than N terms which are nonzero, but [...]
starts to answer my worry a little bit. It really is not the case that there are N true degrees of freedom, we just nominally started out with that many and then gave up certain ones of them.
What I would love to have is a quantitative analysis of the "number of free parameters" in my model after I have fit it, so that I can compare it to (say) a 50-parameter polynomial model that is equally good at reproducing the training set.