There's no such thing as truly learning "from scratch" -- the No Free Lunch Theorem holds no matter what. What you can do is find a sufficiently large (ex: Turing-complete) hypothesis class, and make simplifying assumptions to allow it to be feasibly learnable (such as regularization or priors).
You should look into algorithmic probability for a better foundation.
[0] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.540....
On the other hand, algorithmic probability requires first defining a Turing machine, rendering the Solomonoff Measure defined only up to a specific programming language, which can bias it some arbitrary amount. That's on top of the Solomonoff Measure itself being incomputable, and so utterly useless as a foundation for real-world machine learning and computational cognitive science.
I agree that positing a Bayesian prior on functions/programs/causal structures gets you around the No Free Lunch Theorem. The question just then ends up being: what sort of hypothesis space, and what sort of prior, sufficiently resemble the real world (the data-generating process) to allow for learning from a given data set? That's a matter of science.
I didn't mean intelligence in any abstract problem-space. I meant intelligence in the world and type of problems we humans deal with (in fact, I'm unsure what process should we call intelligence in non-human context).
In the context I'm talking about, we at least have one algorithm that has build models from the scratch: evolution by natural selection.
I was talking about learning the model structure also.
I have been trying to understand FEP, and so far my understanding is that essentially the agent tries to learn the generative model that most closely explains observations and then tries to act in a way that are more likely to cause the environment to generate its preferred observations (say pH and temperature in the right range).
The problem with this approach is in scalability of inference and candidate model generation. By the time you provide model for the agent, you as a designer have coded much of your knowledge already and hence constrain the agent. True AI will build model from the scratch, and not just learn model complexity.