Now that question will open a can of worms! Basically, there is no way to accurately answer that question because there are so many factors involved. That being said...
The "quick" answer is that I wouldn't be concerned until the signal frequencies get near 1 MHz. Between 1 and 10 MHz I would be extra careful. And above 10 MHz I would have a PCB made. Of course there are exceptions, and this is what I would do, etc. But as a rough order of magnitude place to start, it works.
There are many issues involved with this, and I'll try to cover them here...
As others have stated, it's not the signal frequency but the rise/fall time of the signal edges. If you can slow down the edges (but not too much) then you'll have an easier time. FPGA's are great for this because you can change the slew rate and drive strength of the I/O Pins. In a synchronous system, this is more important on the clock lines than the data lines (I'm not saying that data isn't important, however.)
While doing proper signal termination is important, you can't do signal termination without knowing the characteristic impedance of the wire. And in a breadboard type system you won't know what the impedance is, no matter how hard you try. In this case, you'll simply end up twiddling with it until it just happens to work.
Pay attention to the signal return paths and loop currents. This is going to play the biggest part in making the system run fast. Of course, this is damn near impossible to do correctly with a breadboard, but those are the breaks. This is why people use power/gnd planes and 4+ layer PCB's.
I've ran PCIe (2.5 GHz) over wire-wrap-wire for about 5 inches. And I've ran PCIe over a "commercially available" wire for 12 inches. So you can get good performance from wire. It's all in how you use it.
A good breadboard can probably run faster than a bad 2-layer PCB.
Of course, most modern parts are in packages that require a PCB.
Best Answer
You can get automotive-qualified FPGAs. There should be no issues so long as you get one that will work over the temperature range you need and you design the support circuitry correctly. An ASIP may be faster if you build it in silicon, but if the FPGA implementation is fast enough, it's not like it's going to suddenly get slower when you put it in the car. The main 'con' is probably going to be price, but if you're only making a handful then it might be far more reasonable than going full custom.