getBalance() is not working after fast sync as it queries too far into history, is there a way to rebuild all the states without redownload of all the blocks?
The only way to have past intermediate state is to do full block imports without fast sync (i.e. act as an archive node). There's no way to generate your requested data without reprocessing all the blocks.
PS: You don't necessarily need to redownload the chain, you could export it with
geth export chain.dat and then
geth --datadir=somehwere-else import chain.dat. But in general sync time is limited currently by import/processing time, not download bandwidth, so it won't make much of a difference.