We used one of those old lever action bead breakers when we changed the tires on Number Seven. Works like a champ.
We've also got a homemade tire spoon that we used to put the new ones on. It looks like a piece of a girder ground into a rounded shape (and with a handle ground into the end) and the end that you stick in the tire is curved. We were reusing the split rims, though, so they didn't need much finagling.