Why does protein have 4 calories per gram?
Ultimately, the 4 kcal/g numbers come from calorimetry. That is, scientists take a small amount of glucose or protein, put it in a device which burns the material and figures out how much energy is released. Now, this doesn't account for certain factors which complicate matters, such as the fact that humans excrete waste nitrogen as urea and not fully oxidized nitrogen (as is produced in a bomb calorimeter). As such there's some corrections which are applied to account for those differences. When you do the math, you find that carbohydrates and proteins both have about 4 kcal/g energy. As such, most people these days don't actually bother to do the calorimetry to find the energy content, but instead take the content of carbohydrate/protein/fat/etc. and do the calories-per-gram calculation from there.

Now, you're correct that those numbers (from combustion calorimetry) don't match the number you got from the mass balance in gluconeogenesis. Part of the reason for this is that, like most processes, gluconeogenesis isn't 100% efficient. You get some loss as heat due to steps not being 100% reversible. The nutritional content is intended to be more of an estimate of the once-through energy content. (That is, the amount of energy you'll extract if you go directly from the input into a totally metabolized state.)

But perhaps a more important difference is that the mass/energy balance equations for gluconeogenesis from protein can be more complicated than your simple 3:1 analysis suggests -- there's various offshoots of ATP, NADH, etc. generated going from the raw amino acids to glucose. Each of these carries away some energy, and to get a true energy balance. You also need to account for these alternative offshoots of energy. 

Which amino acids you're talking about also makes a difference. Alanine is probably the simplest amino acid to feed into gluconeogenesis. It's transformed at a 2:1 molar ratio, which works out to an approximately 1:1 mass ratio (as expected from the calorimetric ratios). Other amino acids like leucine are ketogenic, meaning that they cannot be converted in gluconeogenesis at all (at least in humans). The differences in how different amino acids metabolize can account for the discrepancy. The 3:1 ratio may refer to a "typical" amino acid distribution, which includes a mix of some 1:1 converted amino acids, some which are only partially converted, and some which aren't converted at all.