Your question: Is there any way that I can build multiple indexes on one table without having to scan the table multiple times?
My answer: I don't think so. Since each index has a different indexing rule, it will analyze the same table in a different way. I've built indexes on a 100GB table recently and it didn't take me too much time (Amazon EC2 with 8 CPU cores / 70 GB RAM). I don't remember how much time it took, but that's a good sign right ;-) ? Painful jobs are always remembered... (ok, the hardware helped a lot).
So, my advice is: get yourself a good maintenance window and just build indexes, remember that they will help a lot of people querying this table.