PaulS:
A different joystick - one that easily works with the Arduino. I typed Arduino joystick into google, and got 2,000,000+ hits. I'm sure one or more of them would to suitable hardware.
Having to add a bluetooth shield or usb host shield just pushed this project firmly into Linux ARM SBC territory. You can get a powerful ARM SBC for $10 that will do everything you need and be much easier to program than hacking together various kludges to make it work with an AVR.