According to what I have read, we have measured the universe to be flat
More or less. I'm happy enough with the WMAP results that indicate that the universe is flat. To be blunt I never thought it could be anything other than flat.
the shape of the universe is directly related to the mass-energy density.
That's what they say. But IMHO two out of three options were always going to be wrong. I always thought it was going to turn out to be flat regardless of the energy density. Which means inflation is superfluous, but that's one for another day.
Firstly, back in the day when the 'big bang' was occurring, wouldn't the mass-energy density be more than great enough to result in a curved universe, if so, how would the universe transition from being curved and finite into being flat and infinite?
Good question. The answer is that curvature does not depend on energy-density. It depends on the delta energy-density. If the energy-density is the same at every point in space, light goes straight.
Secondly, to my understanding GR states that gravity is the result of the curvature of the 3D surface of a four dimensional shape
It isn't. Gravity is the result of a concentration of energy usually in the guise of a star "conditioning" the surrounding space and so altering its metrical properties, this affect diminishing with distance. I don't agree with Prahar that the rubber-sheet analogy causes problems, I think the problem comes from a modern-day confusion between curved space and curved spacetime, where "space is neither homogeneous nor isotropic". See Baez: "Similarly, in general relativity gravity is not really a 'force', but just a manifestation of the curvature of spacetime. Note: not the curvature of space, but of spacetime. The distinction is crucial". Curved spacetime is a "curved metric", and a metric is to do with measurement. For example, you place optical clocks throughout an equatorial slice through the Earth and the surrounding space, then plot the clock rates. You depict lower slower clocks as lower down in a 3D image, and higher faster clock rates higher up. What your plot looks like, is this:
CCASA image by Johnstone, see Wikipedia
That's a picture from the Wikipedia Riemann curvature tensor article. It's the rubber-sheet depiction of curved spacetime. And because it's derived from optical clock rates, it's a plot of the "coordinate" speed of light. Your plot of measurements is curved, space isn't. Instead space is inhomogeneous, and because of this light curves and matter falls down. Note that you need the curvature to get the plot off the flat and level - you need the curvature to get the slope, but the curvature relates to tidal force while the slope relates to the force of gravity which relates to the degree of inhomogeneity.
OK, but it is a shape, so conceptually how can the surface of the shape be infinite in length, width, and depth if to be a shape, the edges/points must meet up and cannot technically be infinitely large, or is this just a conceptual problem of envisioning four dimensional shapes...
Those articles about "the shape of the universe" are nothing of the sort. The conceptual problem is with the universe having an edge. By the way, I don't agree with the assertion that a flat universe must be infinite. IMHO it's a non-sequitur, and it's at odds with big bang cosmology. I don't accept the claim that the universe was already infinite when the big bang occurred.
Or could this problem be solved by having the multi-verse be the underlying four dimensional shape?
No it can't. The multiverse solves nothing. It's pseudoscience, not science.