Underdetermined systems are only underdetermined if you impose no other constraints than the data. Sticking with your example, fitting a 4-deg polynomial to 4 data points means you have one degree of freedom not constrained by the data, which leaves you with a line (in coefficient space) of equally good solutions. However, you can use various regularization techniques to make the problem tractable. For example, by imposing a penalty on the L2-norm (i.e. the sum of squares) of the coefficients, you ensure that there is always one unique solution with the highest fitness.
Regularization techniques also exist for neural networks, so the short answer to your question is 'yes, you can'. Of particular interest is a technique called "dropout", in which, for each update of the weights, you randomly 'drop' a certain subset of nodes from the network. That is, for that particular iteration of the learning algorithm, you pretend these nodes don't exist. Without dropout, the net can learn very complex representations of the input that depend on all the nodes working together just right. Such representations are likely to 'memorize' the training data, rather than finding patterns that generalize. Dropout ensures that the network cannot use all nodes at once to fit the training data; it has to be able to represent the data well even when some nodes are missing, and so the representations it comes up with are more robust.
Also note that when using dropout, the degrees of freedom at any given point during training can actually be smaller than the number of training samples, even though in total you're learning more weights than training samples.