How can I restore my iPhone 4s without getting the newest software?
There are places online where people have kept the IPSW files, if you trust them not to have tampered with this then you could find the right one and when you are in iTunes Option/Alt + Click the Restore button and it will take that IPSW file.

I am not 100% sure if this will work because iOS has to check with the iTunes server and I am not sure if it will activate a phone on an old version... I think it will but can't be sure.