Virtually all jet engines use a technique very similar to the technique you're proposing: the inside of the combustion chamber, turbines, and exhaust, (and afterburner, if the engine has one) as well as the turbine blades and stators, are covered with small holes. Cooling air is forced through these holes, forming a boundary layer between the metal and the super-hot gases.
The temperature of burning fuel/air in a jet engine is well above the melting point of the metals used to build these components, which is why this is necessary. In fact, the temperature of the gases exceeds the vaporization temperature of a number of metals.
Where does this cooling air come from? It comes from the engine's compressor. The reason bypass air isn't used is because it is at a lower pressure than the inside of the core of the engine, so the hot gases would move out through the holes toward the bypass duct. In this case, the boundary layer is made of hot gas instead of cool gas, which destroys the engine.
To get air of adequate pressure, air is "bled" out of the compressor at points where the pressure is high enough to provide adequate flow (in the right direction!) to the parts of the engine that need it. This method of cooling is so effective that the components in a jet engine that need to withstand the most heat are actually the highest pressure parts of the compressor, because (a) air heats up when you compress it, and (b) you can't use the same cool boundary layer technique in the compressor because you need higher pressure air than the hot air from which you're trying to protect the component, and the component is part of the highest-pressure part of the compressor.
Here's a picture of a jet exhaust guide vane, with cooling holes clearly visible:
On a rocket engine, you could potentially cool it with compressed atmospheric air, but doing would add weight and complexity, and would only work in the lower layers of the atmosphere where there's enough air density to provide an adequate mass flow rate to absorb the heat. Since, as you mentioned, fuel (or potentially oxidizer) can be used to effectively cool the engine for a much lower penalty in weight and greater freedom in operating environment, that's been the obvious choice for most high-performance liquid fueled rockets.