If Skype runs on Linux, you're looking at a bare minimum for a gumstix or a beagle board.
Something like an asus WL-520GU router can be combined with a USB sound stick for mic and speaker audio, actually set one up as a web audio stream player, but the video was a serial terminal display. If Skype could run from the command line, without a lot of visual eyecandy, it could be doable.