If a neural network is a universal function approximator, can it have any prior beliefs? Let us confine ourselves to the case where we have a $n$ dimensional input and a $+1$ or $-1$ output. It can be shown that:

For every $n$, there exists a dense NN of depth 2, such that it contains all functions from ${±1}^n$ to ${±1}$. (given sign activation functions and some other very simple assumptions).

Check section 20.3 for the proof.
So, if a neural net can approximate any function, then it has a $\mathcal V \mathcal C $ dimension of infinite (considering the $n$ dimensional set of points as our universe).
Thus, it can realize all types of functions (or its hypothesis set contains all set of functions), and hence cannot have prior knowledge (prior knowledge in the sense used in the No Free Lunch theorem).
Are my deductions correct? Or did I make wrong assumptions? Are there actually any prior beliefs in a neural network that I am missing?
A detailed explanation would be nice.
I think your deduction is mostly correct.

Neural networks of depth are universal function approximators. This means that in principal, for any function of the form you describe, there's a NN that approximates it. 

However, a particular NN architecture of fixed width and depth, with fixed connections is not a universal approximator for all functions. Only an infinitely wide NN is, and that's a theoretical construct, not something you can make in practice.

Typically, a practitioner using a NN injects their prior beliefs about the problem  by selecting an architecture. For example, it is common to use the ImageNet or ResNet architectures for image processing tasks. Those architectures are less effective on other types of tasks. For instance, it should be clear that they are ineffective on say, a time-series analysis task.