For all DVI related stuff you will need a PHY because no FPGA has a TMDS interface. Standard SerDes on Virtex, Stratix of LatticeSC are capable of handling the speed of the DVI link.
The encoding is not that difficult (8b/10b). For the mapping, I'm referring to Silicon Image. They have lots of info.
PAL to RGB: Get a copy of the book Video Demystified (Keith Jack). All the info is in there.