Can I flash an ATMega with a new bootloader using just the normal Arduino board, or will I need additional hardware?
No you need additional hardware. A programmer of some sorts. There are lots of options fro the DIY to the purchased. See the playground for the options you have.
I flashed an ATmega168 without any additional hardware. The only hardware that i needed was 4 jump cables. Check this link:
http://www.geocities.jp/arduino_diecimila/bootloader/index_en.html
It worked perfectly.
That's super minimalistic. I think it will be perfect for me. Thanks.