You can definitely run PHP and MySQL on any number of small Linux boards. I've run Python and SQLite on a Technologic Systems TS-7260, which stores its filesystem on an SD card, and Python and Django on the TS-7500, which actually uses a microSD card. The performance was decent, but accessing the SD card was definitely slower than I hoped-- total page render times were close to 2 seconds. I suspect that might have been more due to Django than the SD card, as I've used other embedded Linux boards that used also used an object relational mapper like Django and a microSD card, and it was quite fast.
Technologic Systems
You might also look at:
For ease of use, I'd probably go with a TS-7500 with Debian Linux on a microSD card, with the Beagleboard and Angstrom Linux a close second. Being able to use a package manager (apt-get for Debian and opkg for Angstrom) is great. I'm also interested to try something that runs Poky Linux, like the extremely sexy (but also more expensive) stuff from Bug Labs.