For the most part, an Arduino version and a USB powered version would be the same. The Arduino has a 5v regulated output.
The main problem is, if the schematic you post is accurate, is that 36Ω resistor, at 4.5v, with average led voltages (red 1.8v, yellow 2v, blue 3.3v) is pushing them past the ""standard"" max current draw of 20mA each. Is that 36Ω a typo?
With 5v, its almost double that. The schematic implies with all 10 led/resistor series on, it's taking 151mA, so 15mA each. The math doesn't work.
Current = (Voltage Source - Forward Voltage Drop) / Resistance
Red: (4.5v - (1.8v * 2)) / 36 = 0.025A or 25mA. (5v - (1.8v * 2)) / 36 = 38mA
Yellow: (4.5v - (2v * 2)) / 36 = 13.8mA. (5v - 4v) / 36 = 27mA
Blue: (4.5v - 3.3v) / 36 = 33.3mA. (5v - 3.3v) / 36 = 47.2mA!
Only the yellow would be mostly safe, without increasing the resistance. Simply an extra resistor between 24~68Ω in series with the existing 36Ω for each led strand, would solve this with a maximum draw of 28mA to 16mA per strand. That's how you can protect the leds when using the USB power supply.
Now if you are going to power the leds from the Arduino, directly tied to the Microcontroller's pins, you will quickly eat through the 40mA per pin limit, or 200mA total limit. Especially on the blue section, where you have three leds in parallel. That's 47mA with the existing resistor, less if you add another resistor per led, but you would only be able to have 4 of the sections on at a time. In this case, if you need more, you would need a transistor with a resistor as well.
simulate this circuit – Schematic created using CircuitLab
The SW1 is the manual switch you have. The two 36Ω resistors are the same as a single 72Ω. The three leds are standard 3.3V Blue leds. The NPN transistor allows you to switch more current per pin than directly connecting them would (The 2n3904 tends to allow up to 200mA each). The 1k resistor provides ~4.5mA of current at the transistor base, which should saturate it.
In any case, with a bit of math as listed above, you should have all you need to figure any combination you need out.
The 5V rail will most definitely be able to supply the power that you need in your setup. For most ATX PSUs, the +5v rail has the largest current capacity of all rails on the supply. Many, if not most devices will charge as soon as there is a voltage applied to their USB port, so I'd say that aspect of your setup is also good. I wouldn't worry about a device overdraw; the current control is generally built into the device rather than the charger.
The only thing to really consider is similar to what you mentioned in your question; some devices will begin to charge at say, half of their current capacity, and only ramp up to full current once they've received some data from the charger/host device. But, this is only really an inconvenience, and most devices will charge with at least some initial current. The only device I can think of off the top of my head that won't charge at all without this enumeration is a Sony PlayStation 3 controller (but I'm sure there are more).
The final point is that this really just varies on a device to device basis. Some devices will charge with max current right off the bat, a few will be limited to initial max current, and a couple might not charge at all.
Best Answer
TLDR; Yes, but it is always a good idea to put a smoothing capacitor across the Vcc/Ground pins of the IC, and try to put that capacitor as close to the pins as possible.
Longer answer:
The USB standard specifies that a "charging port" should be able to supply up to 500mA at 5 volts...
http://en.wikipedia.org/wiki/USB#Charging_ports
The voltage required by the chip depends on what speed you are running at, but even at the maximum speed of 20MHz it only needs 4.5 volts...
...so you are good on voltage.
The chip is also spec'ed to pull an absolute max of 200mA of current...
...(and that would mostly be from driving output pins), so you are good on current.
So, at least in terms of voltage and current everything looks good, but there is also the issue of noise. This noise can come from either the power supply or can be generated by the chip itself as it makes very fast changes to the amount of current that it requires (for example, at the instant you switch a bunch of output pins from 0 to 1).
As far as the noise coming from the charger, all USB chargers are not built equally. I tested a few crappy USB chargers to see how noisy the output was...
http://wp.josh.com/2014/12/09/a-tale-of-four-usb-power-supplies/
Here is one of the worst...
So the real concern here is that some of that noise (the jigglyness of the voltage) could cause the cause the chip to glitch.
A filtering capacitor across the power leads can help smooth this out. It is typically recommended to put a couple of uF of capacitance across the power leads where they enter your circuit to filter this kind of noise.
It is also generally recommended to put a smaller decoupling cap across the power supply pins, and to put this cap as close to the chip as possible to smooth out the very quickly changing power supply demands of the chip.
Much has been written about how to pick the correct decoupling capacitor size and type, including...
http://www.intersil.com/data/an/an1325.pdf http://www.atmel.com%2FImages%2FAtmel-2521-AVR-Hardware-Design-Considerations_ApplicationNote_AVR042.pdf Atmel AVR042: AVR Hardware Design Considerations: Providing robust supply voltage, digital and analog. Choosing and Using Bypass Capacitors: Application Note
...but a good guess for decoupling cap for a chip like this might be about 0.1uF.
All that said, in practice I've found AVRs to be remarkably tolerant when it comes to power supply, and I've also found name brand USB chargers to be high quality and smooth. You can often just use what you've got and putting, say, a 1uF across the power supply pins will usually eliminate any problems- especially if you are just bread boarding and not designing a commercial product. It is also a good idea to use the on-chip watchdog to reset the chip just in case you ever do have problems due to power supply issues (it also saves you from other problems too).