My feeling would be to try and avoid using 5V parts. For instance, the Intel Quark 1000 is a 400MHz Pentium-class CPU being aimed at microcontroller applications. It probably isn't quite as easy to manage (it's a BGA package not a PLCC) but is rather more modern.
The Quark itself is a bit of a camel, but it's the modern equivalent of a386. The alternative would be an Atom, VIA or some other 'embedded' x86 processor. All of these might be harder to handle than the slower 386 though. The Quark comes on the Intel Galileo board which can be connected to the Cyclone V GX via PCIe, which is one way to join them.
I'd suggest the OP avoid making an FPGA board: a 6/8 layer board with a ton of low-voltage high-current FPGA power supplies, BGA escapes, signal integrity etc, is a somewhat more complex endeavour than a basic-ish 2/4 layer board to hook into an expansion header on the existing board. Not least because you can design that in a free/cheap tool, you don't have to pay for fancy PCB tools, and you can get it fabbed anywhere.
I very much doubt it'll be possible without level translators, which doubles the complexity of the addon board.