OsloGin - any idea how much you would need to store?
Not sure why you are avoiding cloud storage - if you have a GMail account, or Outlook (Hotmail / Live.co.uk / Microsoft) account you get some free file / document / video / photo storage. (limited to 5 GB or 15 GB depending on which company and what their rules are)...
Microsoft plans to give unlimited storage for Office 365 subscribers (not sure if that is current now in UK, or coming later this year). Some mobile phones get you 50 to 100 GB of online storage. My Android phone (Galaxy S II) automatically uploads photos when I take them (I have unlimited data plan).
With Google Drive there is software for Apple and Windows (I use this on my iMac) which will keep the Google storage in sync with documents on your computer (so long as you have an internet connection).
If I save a new document (quote, invoice, job specification) on the iMac in the correct folder, it gets copied away to the Google Drive too, so acts as an automated backup system. I won't claim these things are perfect - I have a 2 TB Buffalo NAS on my LAN and run the iMac 'Time Capsule' backup system too... just in case
Note I have over a dozen systems here and relatively few of them have backup running (simply because I use them mostly for browsing and I routinely put client invoices online for them to view/ print, so that's my 'backup' anyway :)
I'm also considering (once I've found a suitable backup application for my needs) using Amazon's Glacier service to store hundreds of GB of files (for an annual cost below 25 quid). That one is aimed at backup much more than retrieval (ie cost for retrieving is much higher than storage and uploading) as this is for the 'disaster recovery' situation when the first wiped out everything at your home/ office and you can then pull back everything from the Glacier (it's slow retrieval and storage, whereas The Box, Carbonite and similar cloud storage systems have fast up/down loading for quick transfer {but quite costly if you have 100s of GB to store } ).