I haven't actually implemented this (so there might be some problems I'm not immediately seeing), but I thought I'd try to help.
Here's what you said is happening:
Client A sends input at T0
Server receives input at T1
All clients receive the change at T2
At T2 however, using client prediction, Client A is now at a position appropriate to T4.
It probably would be useful to think in terms of server time. Its (probably) very similar to how interpolation works.
Every command is sent up with a server time. This server time is figured out at the start of a match by querying for the server tick, compensating for ping time. On the client you have your own local tick count, and each command you send up is converted to server ticks (it's a simple subtraction operation)
Also, the client is always rendering "in the past". So you assume that the world the client sees is, say, 100ms behind what the server's time really is.
So let's rephrase your example with server time (designated by S).
Client sends input at T0 with server time S0 (which I'm guessing is really "client representation of server time minus interpolation time"). Client doesn't wait for response from server and moves immediately.
Server receives input at T1. Server figures out client's authoritative position at server time S0 given by the client. Sends that to the client.
Client receives the authoritative position at T2 (still with designation of server time S0). The client keeps track of some past amount of time worth of previous events (probably just a queue of all unconfirmed predictions).
If the predicted position/velocity/whatever that the server sends back at S0 is different than what the client has stored at S0, the client handles this somehow. Either by snapping the player back to their past position, or resimulating the previous input, or maybe something else I haven't thought of.