Easiest and Best PoE Ethernet Chip/Micro/Design for DIY Interface with Custom Arduino Board (AVR Solution)
You really haven't given us any actual information to help you with other than you don't want an Arduino shield solution. What kind of power supply do you need? How many voltages, and at what current levels? Are you just powering the AVR? Do you need galvanic isolation?

I have successfully used National's LM5071 PoE PD controller in one of my designs. Depending on how you want to hook it up, it'll give you full galvanic isolation and multiple output voltages. My particular setup gives me 3.3V at 2A and a separately-isolated 5V at 1A. I "slave" an LTC3523 off the 3.3V to give me 1.8V and 5V supplies that aren't isolated from the main 3.3V supply.

Many companies offer PoE PD controllers. National, Maxim, Linear Tech, TI... Have you done any poking through their websites to see what's out there so you can narrow down your search?

EDIT now that I have more information from the edited question. :-)

TI's TPS2370 looks like a perfect fit. It's an 8-pin SOIC device that takes care of the 802.3af spec part and you can drive pretty much ANY regulator off of that. So a really simple supply would consist of the TPS2370 and something like the BD9001 (personally I like Linear's LT1676 but I don't think it has a high enough input voltage spec for PoE) from the previous answer. Two 8 pin SOIC devices, a handful of passives and a small inductor would get you what you're after.