ATMega644PA possibly bricked by setting fuses with avrdude
Nope, your 0x63 setting on the lfuse byte has selected the internal 128kHz oscillator as the clock source.  (bytes 3..0 are CKSEL, see table 7.1 on p.28 of the ATmega644 datasheet where 0011 is 'Internal 128 kHz RC Oscillator').  This is nice and low power, but it means that your programmer likely isn't clocking itself slowly enough to program your device. I'm not familiar with either avrdude or the STK500, but this is where your problem is coming from.

However, it will be difficult for you to brick your chip, because you've got the STK500, which can do high voltage programming and rescue it from most situations.  As I've never used the device, I'll defer to the many other threads where others have posted problems and solutions for AVR fuse settings.  There's also one here on Chiphacker (see my comment.)

Next time, this fuse setting calculator is a nice resource.  It's fantastic that you read the datasheet, and tried to calculate what you wanted yourself, but the tool makes it much easier. 

BTW, what were the fuses set to before you made the change?

Edit: Looks like the 'A' option just indicates that it's not a member of the "*P*ico Power" series, so that shouldn't make a difference.