I did a lot of work with radios in the military. Cell phones that use 3/4G is actually coined from a term used to describe 3rd/4th Generation ALE. ALE is a technology that allows radios in a net to obtain their own unique ID. (like an IP). Usually they use HF frequencies (which can broadcast over the horizon, and thus are not line of sight). Before ALE you were looking at 0.24Kbps (analog signal) for a single channel ground radio system. However, with sustained HF communication, you can get much higher bandwidth like you do today on your cell phone.
I guess my point is that to rebuild an internet segment, you want to create a WAN, right? You could use a physical medium like fiber or ethernet, but that would be a lot of digging and re-use of wired technology that requires a lot of maintenance.
I would imagine the first 'internet' in a new world would consist of sending digital signals through radio communications. Provided people are hosting information using TCP on port 80 (standards), and repeating signals received to cover more ground, i think that would be the most feasible way to create a slow but working internet.
I believe the FCC is looking at releasing a bunch of C frequency bands traditionally used for satellite transponders, weather and long range tracking; to the open market for development of access points much like the ones in your house. However they will offer greater distance and higher bandwidth than the current 4G implementations of ALE. I believe these higher frequencies will be used more in the future, as a higher frequency allows more digital bits per wavelength.