The city of Toronto has a new program where you can rent a bike locker from them. It's $10 a month (!) and it's big enough to put your entire bike in, and shoes etc.

Check out the information:

http://www.toronto.ca/cycling/locker.htm

If there is enough interest, I'm sure they will put more!