A bunch of 74HC595 chips will work great. Other chips that would also work just as well and perhaps slightly better are listed at: Which SIPO chip is better, 74HC4094 or 74HC595 or something else?

2. The Arduino is an excellent choice for prototyping, especially if you are comfortable using gcc. Perhaps it would be quicker to use one for now. Alas, I suspect you will soon write code for this POV display that needs more RAM than the Arduino has available -- at that time, either (a) use one or more of tricks to reduce the RAM needed, or (b) add some external RAM, or (c) port the code to some other microcontroller with more RAM (perhaps the ATMEGA1284 ?).

The Parallax Propeller is an excellent choice for a high resolution POV display -- it has an order of magnitude more internal RAM (32 KB RAM) than the ATmega238 in the Arduino. (Is there anything I can do to support porting gcc to the Propeller?)

Some people prefer "square pixels". I'm sure you already know that the distance around the equator of a sphere is twice as long as the distance from pole to pole (Earth's equator is a little more than twice as long). Since you have 64 pixels from the south pole to the north pole, you might choose to reload a new vertical "line" of pixels 264 = 128 times per revolution in order to get 128 "square pixels" at the equator. The simplest way to do that is to store the full frame uncompressed in RAM. That requires 64128 pixels * 3 bits/pixel = 24 576 bits = 3 072 bytes, plus a few bytes of RAM for other program variables. Alas, the Atmel ATmega328 in the Arduino only has 2 048 bytes of RAM.

Earlier POV displays used microcontrollers with an order of magnitude (!) less RAM than this. So people have developed a variety of tricks you can use to work around this. One trick: Only lighting up the "front" half of the globe turing the time you can see the LEDs, then turning off all the LEDs (or leaving them on some constant color) during the "back" half that you can't directly see the LEDs. That halves the amount of RAM you need, so then it fits in the Arduino. If you don't like that trick, there are other tricks you can use that are less obvious. Another trick: Store the image in the flash program memory. The Arduino has enough flash program memory to store several 3 072 byte frames. Yet another trick: use ASCII text to store the text you want to display, then use flash program memory to store the "character generator ROM" data. I'm pretty sure there are other POV tricks ...

3. If I were building it, I would power the Arduino and the 74HC595 chips from one big power supply, and power the motor that spins the POV from a separate power supply.

Only after I got all that working would I even consider a more complicated separated power supply system. (In principle, if you have a separate "red" switching power supply whose +V is only connected to 74HC595 chips which in turn are only connected to red LEDs, you could independently tune its output voltage to minimize the total power and heat production of the system. But it seems unnecessarily complicated.)

4. and 5. Perhaps the simplest way for the Arduino to drive the POV display is to daisy chain all 24 74HC595 chips in one long single string, and then use the Arduino SPI library. That requires 192 clock pulses to clock in the new column of data, and then a pulse on the RCLK (aka framing pulse, SS, etc.) to start displaying that new data. According to one Arduino to SPI interface tutorial, the fastest SPI clock rate is system speed / 4. So the 16 MHz Arduino can put out a SPI CLK of 4 MHz. If you upgrade it with a 20 MHz crystal, you can get a SPI CLK of 5 MHz. If you can get your program fast enough to keep up with the SPI hardware, you can put out a new column, at best, in 5 MHz / 193 pulses, so the maximum theoretically possible speed is 25 907 columns/second.

At the standard cartoon film refresh rate of 24 frames/second (which flickers noticeably -- you would like something better), and at 128 columns/frame to get "square" pixels at the equator (you might want more to get better resolution), that gives 24 frames/second * 128 columns/frame = 3072 columns/second.

There's nearly an order of magnitude of breathing room between "the speed you want": 3072 columns/second, and "the speed that is completely impossible on Arduino hardware": 25 908 columns/second. Hopefully that gives you enough room.

Some people think you can get a faster column refresh rate by re-arranging the 74HC595 chips into 2 or more chains and loading all chains in parallel. Some people are like that -- they see unused pins on the Arduino, and they are itching to use them for something. But it may be counter-productive -- the SPI hardware is only connected to one set of pins on the Arduino, and so chains hooked to any other pins must be loading with emulated "bit-banging" software, which will invariably be slower and use more CPU time than the built-in SPI hardware.