Also things like pain, hunger and pleasure also are for the most part generated outside of the "learning" parts of the brain, so similar to a pre-defined utility function/oracle.

Yes a 1yo child has a good way of getting feedback from the environment when learning to walk. They fall and it hurts !

But who teaches the previous generations and how? Chicken or egg first?

I think the origin is communication and memory. When a being (X) signals to another being (Y) the origins of its pain (signal of increased death probability) and X and Y can remember this cause, they can begin to teach.

Very little of what human's learn is done "unsupervised".