ironspider:
My completely inexperienced thought process was that I would need some kind of 5v voltage regulator capable of handling like 4Amps (since I imagine the $4 wall-wart PSu from ebay is not regulated), some caps to smooth that, a PoT, the ATtiny85, the LEDs and something (transistor? relay? MOSFET?) that can handle controlling these LEDs other than the ATTiny85?Am I on the right track here?
Yes. The 5V power supply for the LEDs does not need to be well-regulated, but if it isn't then you should use a separate power supply for the Arduino. Use a logic-level mosfet to switch the LEDs from the attiny. There are lots of suitable mosfets, such as IRLU8726PBF.