Powerline Adapter with PoE Injector (~$60)
Update 10/19/2017
A year later, I wholeheartedly recommend a Powerline (aka Homeplug) adapter with POE, rather than a wireless bridge. I still haven't found any wireless bridges with POE out for less than $100, but in the meantime, the handful of COPS-928-POE have been working great. I definitely recommend this option for connecting remote IP phones. This is a decent option for remote security cameras as well.
The idea behind PoE was to make it easy to send power to devices where you had Ethernet (or could easily wire Ethernet), but no power, but if you happen to have power, but no Ethernet at the place where your PoE-powered device needs to go, a POE PSE Powerline adapter is a better option than a wireless bridge. The Powerline adapter sends its signal via the existing electrical wiring in your house, and will generally encounter less interference than a wireless adapter (unless you have a lot of AC motors running, like vacuum cleaners or heavy machinery).
The TP-Link AV200 Nano has been working great as the other end of the Powerline bridge, by the router. This end of the Powerline bridge doesn't need PoE out, and the AV200 adapter is cheaper than the higher-bandwith AV500 adapters (and later). An IP phone doesn't need much bandwidth, so the ~70 Mbps supported by the AV200 is plenty.
Original Post:
After several hours of research, I'm feeling pretty confident that a wireless bridge with a built-in 802.3af PoE injector doesn't exist except for industrial applications. However, you can get a Powerline ethernet bridge with a built-in POE injector, though they can be a bit harder to find.
Side note: no, I am not getting EoP confused with PoE. There really are devices that can go from EoP to PoE in a single unit.
The lowest-clutter solution to connect the phone to the network and provide PoE is a Powerline Ethernet Bridge with PoE Injector, such as the Comtrend Powergrid 9141s-poe Powerline Network Adapter or the COPS-928-POE, available on eBay.
Low clutter: the only item close to the phone is Powerline adapter. The phone connects directly to the Powerline adapter, which outputs 802.3af, so no need for a separate PoE injector. The only cable is the Ethernet cable going from the phone to the Powerline adapter. There's not even a power cord, since the device is a wall wart.
This is slightly more clutter than a wireless bridge, because you also need a Powerline adapter near the router that is compatible with the Homeplug AV standard, such as the TP-Link AV200. But at least the extra clutter is with all your other network equipment clutter, instead of cluttering your desk.
Easy setup: Since this solution is for a home user who will probably need to set it up himself, you want the simplest possible setup. Powerline is plug-and-play: just plug in both adapters and push the button on each one to connect them.
Better for phones anyway: Powerline has less packet loss than WiFi, which means better call quality [citation needed].
UPDATE (10/24/2016) I tested the COPS-928-POE paired with TP-LINK AV200 Nano. They established a link within seconds after plugging them in. COPS-928-POE powered up my phone right away, and my phone connected to the server a few seconds after the two Powerline adapters established a connection with each other. I hit the security button on both adapters to establish a secure link, and everything reconnected again within 15 seconds. There was no noticeable difference in call quality, compared to my Ethernet connection. Since they are now paired and ready to go, I will be shipping the pair to the home user, confident they will be able to get these set up fairly easily.
