The way I understand it, Verizon's LTE is a third and a half generation network, beyond 3G, but before 4G. Therefore 4G referring to the Verizon network is not factual (though that won't stop marketing), and I don't know of anything in the mix for a 3.5G AT&T network.
When Apple named their second iPhone the iPhone 3G, they were referring to the third generation cellular network it ran on, not that it was the third generation of the iPhone. A quick look at the iPhone article on Wikipedia gives no explanation to the iPhone 3GS name.
I believe the name iPhone 4G is out, because even though it is the 4th generation, it doesn't run on 4G networks which would cause confusion. Historically, Apple seems to marked generation-named items the other way around, for example the G3, G4, G5 processors.
iPhone HD is also out, as it's hardly high definition by the current meaning. High definition for a smartphone, sure, but so is the current iPhone. Plus, it just have the "Apple product ring" to it. For example, iTablet.
I personally would like to see them return to the name "iPhone", but I doubt that'll happen as the iPhone 3G sounds superior to the iPhone.
How about "Mid-2010 iPhone". Well, I suppose we'll see on the 7th, won't we?
EDIT -
This wouldn't be the first time Apple named a product after it's processor though. PowerMac G4, etc. Or a specific feature - iMac DV.