After a iPhone is stolen, can that device's iCloud backup be accessed? I had an iPhone 4 stolen from me and there is an associated iCloud backup with tons of data I want. Is there any possible way to access this without the iPhone 4?

I also got an iPhone 5 recently but don't think the restore will work (but haven't tried).
Apple doesn't expose iCloud backups directly to end users via computer or web interface, but you can restore that backup onto pretty much any other iOS device.

The new iPhone (or any iOS device for that matter) has iOS version the same or newer than the version backed up from the stolen phone. Simply erase all content on the current device (losing everything in it) and restore your old backup onto the device. 

Hopefully, have not "created" much new data on your new phone and don't have to write down many new contacts or items or export any documents before you erase it. However, you could always back that device up to the same or different iCloud account or to iTunes and restore that once you've gotten your data to a more portable form.