This is my second answer. It is an attempt to clarify some points in my first, obviously not very popular, answer and to add a couple of additional points that are still appear to be missing in many good answers from other people.
So, again, where did the energy lifting the brick come from?
Most people, including myself, agree that the source of the increasing potential energy of the rising brick is the decreasing potential energy of a column of air coming down.
Some use the term "buoyant potential energy", but that it is just another, less direct, way to express the same idea: the fact that the column of air "wants" to go down can be interpreted as a balloon "wanting" to go up.
OK, so, where did the potential energy of the column of air come from?
Here the opinions differ.
Some people suggest that it comes from the act of inflating a balloon. Others say that it is somehow a property of helium. Others - that it is due to the gravitational field. Some don't say anything.
In my unpopular answer, I said that this potential energy is "built into the atmosphere and therefore has the same sources as the potential energy of the atmosphere, which is, mostly, gravity and sun". This answer was mostly downvoted and the arguments around it continues to this day. So, I'd like to clarify what I mean by "potential energy built into the atmosphere" and why I think it is a correct answer.
If we choose the sea level as a reference (zero potential level), we'll need to lift air molecules up to give the atmosphere any positive potential energy. This is achieved by heating the air. If, today, we increased the temperature of the atmosphere, it would expand and its potential energy would increase. If we cooled the atmosphere, it would contract and its potential energy would decrease. If the temperature somehow became zero, the atmosphere would collapse and its potential energy (relative to the sea level - our reference point) would become zero.
So it takes both gravity and heat, not just gravity, to build up the potential energy of the atmosphere.
The expression "potential energy built into the atmosphere" just reflects the fact that air molecules, suspended at various heights above the ground (due to their kinetic energies or temperature) and making up the atmosphere, have some combined potential energy - the potential energy of the atmosphere.
Can we say that the energy came from the inflation of a balloon?
Sure, we can say that by inflating a balloon, we displace (lift) a certain amount of air and, by doing it, we increase the potential energy of the atmosphere, but, it does not mean that this particular energy will be used or will be needed for the column of air to go down or the balloon to go up.
If, while inflating the balloon, we sucked in and compressed (or otherwise remove) ten times as much air as goes into the balloon, the column of air would still go down and the balloon would still go up.
So, if the potential energy that is used to lift the balloon is already built into the atmosphere, what is so special about helium that makes the balloon rise? Why would not air in the balloon would do the same?
Here comes a trickier part of the answer: in order to make a column of air go down, we just need to create some room for it, which would open a path for reducing its potential energy - otherwise, its potential energy would not decrease, transfer or otherwise be realized.
As an example, instead of inflating a balloon, we could compress some air and that would allow a column of air to go down.
As another example, we could untie a piece of wood stuck at the bottom of an ocean and thus release some potential energy stored in the water column above it.
A balloon filled with air just does not create that room, since replacing it would not reduce the potential energy of the air column above it.
So, the problem with the balloon is not only about the source of energy, but also about a method of releasing or transferring the existing potential energy.
The amount of energy spent in the process may be about equal (energy for inflating a helium balloon), greater (energy for compressing air) or smaller (energy for untying a piece of wood at the bottom of an ocean) than the potential energy being released.
In other words, the explicitly spent energy in the process of making room for the column of fluid to go down and release/transfer its potential energy, is incidental - not essential - part of the energy release/transfer.