Setup iPhone as new (by resetting all contents and settings) Don't sign in to iCloud. Don't do a restore. Select "Setup as new iPhone". Search settings for the update. Then if you want you can go ahead and reset all contents and settings from the general settings menu and restore from iCloud afterwards.
Or you can hold the power and home button together. When you see the Apple logo, release the power button but keep holding the home button. It'll tell you to connect to iTunes via cable. From there select upgrade or restore (can't remember what the specific wording is). iTunes will install the most recent software.
Edited for clarification.