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.
No, there is no way if have deleted the old
getBalance is supposed to work even the state is saved in the very first block.
However if you still have the old chain data folder you can replace it to get the old state.