Conservation of energy entails that all energy in the present has existed for all time. Therefore, this implies that the big bang was initiated with preexisting energy. Where did this energy come from?
There is no energy conservation in General Relativity which can be seen for instance at the big bang (as OP mentions). But also the redshift / blueshift of a photon due to expanding or shrinking of spacetime violates energy conservation.
The Noether theorem tells us that a conserved quantity (energy in your question) is connected to a symmetry (time translation symmetry). Since this symmetry is not generally true in GR (e.g. at the big bang, the creation of spacetime itself) energy conservation does not hold.
Sean Carroll has a nice explanation on his blog. http://www.preposterousuniverse.com/blog/2010/02/22/energy-is-not-conserved/
The answer to this is the same answer to the question: 'Where did all the material in the universe actually come from in the first place?'
And that answer is: At some point, all of it must have literally popped into existence from absolutely nothing.
EDIT: Some may try to claim it's ALWAYS been there. But that doesn't change the fact that, at some point, all energy and material literally must have popped into existence from nothing. Because before the alleged Big Bang, there probably existed only infinite space. Infinite space has ALWAYS existed (why literally infinite space exists in the first place is another brain-melting debate), but all material and energy has not always existed.
At the very LEAST, the primordial singularity, that alleged point smaller than an atom which contained all the material and energy in the universe, must have popped into existence from nothing.