If speed and timing accuracy are not important you can use AVR chips with no external crystal (certainly I've used many this way, can't remember if I've used the 328 though). All that is needed is a few caps (and on a breadboard sometimes not even them because the BB capacitance is so high :))
Still, as westfw says, for $5 you might as well get a proto board to start with to remove a few variables.