If tire levers don't work, I'm not sure what to tell you about trying to remove them...but if you ever do get the tires off, soapy water on the bead should make it easier to put 'em on (this works on my moped tires, anyway).

I have big, heavy-duty, metal tire levers for my moped...I wonder if that's what would be best for your evil tires of doom?