too few data while too many degrees of freedom in linear regression
Good question. The solution lies in understanding how weights play into the model's prediction. I've glossed over a bunch of issues here, but the big picture is what is most important.

Theory


When you create a model all the weights are psuedo-randomly initialized. This solves your problem of not having enough degrees of freedom to solve a linear regression. We've interpolated our weights and our model will update only the weights it needs as it trains. 
Additionally, your model will probably find that most of your weights converge to zero. If you are using sklearn's load_digits() function, I recall that about half of each image was just white pixels. It is likely that there is a significant percentage of pixels that do not matter across all images (and thus might be assigned a weight of zero). Your question of how can you trust the prediction of the model is thus answered and we can modify our statement about degrees of freedom to: There cannot exist a greater number of discovered statistical trends than there are data samples. It is hard to measure "number of discovered statistical trends", but it follows that there is a finite number and that they are less than the number of samples minus 1.


Example

With a fully-connected, shallow neural network consisting of the input layer with weights and an output layer with two neurons, the input to the activation function of each of the output neurons will be something like the following:

$$f(B_1+\sum_{i=1}^{i}W_i*{I_i}_A)=P$$

where 


$P$ is the class probability, 
$B_1$ is the bias of the output layer, 
$W_i$ is the weight of a specific neuronal connection, 
${I_i}_A$ is the output of the connected neuron if activated (in this case the pixel value), and 
$f()$ is the activation function of the output layer neuron.


If we didn't initialize $W_i$ to something/anything, we would be unable to solve the equation (more variables than samples). However, by randomly initializing them, the equation immediately becomes solvable and we can use stochastic gradient descent or a different algorithm to optimize our weights. I hope this shows how pseudo-randomly initializing $W_i$ solves the mathematical problem of degrees of freedom.