It turned out the installation of apps over the air in iOS 7 really needs an internet connection now. The iPad tries to contact at least the following URLs before installing the app.
ax.init.itunes.apple.com: The device obtains the current file-size limit for downloading apps over the cellular network.
ocsp.apple.com: The device contacts this site to check the status of the distribution certificate used to sign the provisioning profile.
It seems in iOS6 it was ok if those URLs were not reachable and now in iOS 7 they have to be reachable.