My initial reaction when reading it was that it's really weak, but others have pointed out that it could end up being like Rebuild. Even if you manage to connect Redistrict with Estate/Duchy every hand, and the Redistricts never collide, you wouldn't have four Provinces until turn 11 (open Redistrict/Redistrict, eight turns or redistricting Estate into Duchy or Duchy into Province, and one turn to buy a fourth Estate), and that was both assuming perfect shuffle luck and assuming that you get a Redistrict in every hand, which I don't think is possible without buying a third Redistrict. After that point, every new Province is going to take at least 3 turns (one to buy an Estate, then two turns to turn it into Province), which seems pretty slow.
If you have it cost $4, you can't open doubles (except with Baker, but that's just one combo), which I thought would slow it down a lot but now that I'm thinking about it maybe not. It might be the case that opening Redistrict/Estate and grabbing a second Redistrict later is almost as good as opening Redistrict/Redistrict and grabbing a fourth Estate later.
I think the big problem with this card is that most boards with Redistrict will be such that either you go for Redistrict and nothing else, or you ignore Redistrict. There are some interesting things you could do with it with a big hand size though.
Another problem is that if the monolithic strategy turns out to be strong, it will be very, very luck-dependent, since having two Redistricts collide can set you back a whole shuffle. Having it top-deck instead of discard would fix that problem, and then it would fix it even more by making the monolithic strategy be very slow anyway. Or maybe it actually wouldn't slow it down? You could just buy Redistricts whenever you can, because they won't collide (if you do you just top-deck them). Drawing a hand of four Redistricts and an Estate wouldn't make a difference at all; you just expand the Estate, and put back three Redistricts, next turn expand something else and put back two Redistricts, etc.
I keep thinking I have opinions on this card and then convincing myself that I'm wrong, so now I don't know what to think.