Possible causes of dead cyclone IV on custom board
3.3V on a 2.5V IO bank probably won't do any harm. The datasheet will tell you, but most of the Altera parts at least since the III series (Stratix/Cyclone/Arria) are 3.3V tolerant on 2.5V banks as long as ringing is controlled (3.6V is the abs max usually). The datasheet will confirm or repute this (you have read through I/O and power sections of the datasheet right?).

If you have shorted out pins, it may have done damage, especially if some power rails are shorted but others aren't. FPGAs typically like their power rails sequenced in a specific order.
If the FPGA is un-programmed, shorting the IO pins to each other is likely to cause no harm as they default to inputs. However if you short the IO pin to VDD and don't apply any voltage on VCCIO, this could cause damage to the IO buffers as it puts them way out of spec - it will possibly fry the protection diodes and possibly other things, who knows.

You've soldered/desoldered the FPGA several times and in each case likely not following the specified thermal ramp up/down specifications (measuring the top of the chip tells you little about die temperature). Using a heat gun also causes the top of the chip to heat up much faster than the bottom which can in turn result in thermal damage.
For one time soldering on a prototype, not following those will likely cause no harm (it may, but probably not). However putting the chip through multiple thermal cycles using a heat gun can cause damage (I've personally killed a few ICs reworking them multiple times).


Additionally, failing to connect the thermal pad can easily cause malfunctions. I don't know about the Cyclone IV specifically, but I've come across several ICs which fail to work correctly without a pad connection.
It is also possible that there were additional bridges or cold joints that you didn't spot. Reworking multiple times will beca(use of reduced flux unless you added more) cause the solder to flow less well increasing the number of cold joints.