It won't be cheap, but it doesn't have to be all that expensive either. The seats and center console are a must, but most everything else can be done with vinyl dye. As long as you use quality dye, and proper technique, you will get high quality, permanent results.
The seats can be as low as $650 for a complete set, and the console can be from $300 to $450. A carpet can be difficult to do dye, and will cost between $100 and $300. The seatbelts should also be replaced, but I'm not sure how much this costs. A few small pieces on the door panels will need replaced as well, and again I don't know the cost, but it isn't much. If you're careful, you can do the headliner quite well with vinyl dye. All the rest of the plastic trim can be recolored as needed.
With the money you save this way, you can invest in all the little things, such as the rearview mirror, the cigarette lighter, the space to the left of the instrument cluster, the lights on the front doors, and the lights just above the rear doors. I'm not sure, but I believe the sunvisors are slightly different on the impala as well (anyone care to verify?).