Why don't you think the PLL will lock? It should, but you will just have to work a little harder. The ALTPLL_RECONFIG Megafunction can be used to program the feedback parameters of the PLL and phase-shift the clocks.
If you have another reference oscillator clock, eg. 125MHz, you can use that to measure the frequency of the variable frequency incoming clock. For example, I have a design where I pulse a control line (for a ~100ms) and count the number of 125MHz clocks and number of reference clock periods during the pulse high time. Then with that I can estimate an external reference clock frequency. In my case, I am just confirming it is the frequency I expect. In your case, you would use the measured frequency to then determine PLL settings, and reprogram the PLL via the ALTPLL_RECONFIG interface, and check that the lock signal locks.
Then you can pulse the phase shift circuits on the PLL and capture data. If you know what the data is supposed to be, then you can perform a sweep such that you get bad data, then good data (hopefully at multiple settings) and then bad data again. You then move the capture location to the center of the eye pattern.
Take a look at the ALTPLL_RECONFIG function and see if it will work for you.
Depending on the FPGA you are using, there are also delay elements in the FPGA IOEs. I recall seeing a program MORPHIO I believe ... yes, this document,
http://www.altera.com/literature/wp/wp_morphio_reconfig.pdf where they used JTAG commands to manipulate I/O settings. If this scheme allows you to change IOE delays, and there is enough delay range to meet your timing requirements, then that might be another option for you.
I would recommend the PLL option though, as that has direct support, and you'd likely get help if you could not figure out how to use that method.
Cheers,
Dave