Capability needs to be answered, agreed.
The answer is ships and submarines that can fire long range land attack cruise missiles? I don't follow the logic but I suspect I know what you are thinking.
To use a medieval analogy - the counter to a sword isn't another sword, it's a shield. Of course, you do need to have a sword too but it's the shield that needs to be tailor made for the opponents sword. Likewise, your sword is designed for the opponent's shield.
So how do you counter Brahmos in my opinion?
1. Shield: Ship- and shore-based air active radar homing missiles (NOT semi-active). It is extremely likely that these missiles will be used in swarms and they fly really fast, so you need to be able to direct your defense missiles in parallel.
I think
@Bilal Khan (Quwa) has already pointed out how the the PN Milgem and the Jinnah's will focus on this anti-missile air-defense role as opposed to the 054AP's, which will focus on anti-aircraft air-defense role. In their current configuration, it is the Milgem that will form the most effective shield against Brahmos.
2. Sword: This is probably what you are thinking as the answer to India's capability. Of course, it is a part of the answer.
A. So we need to hit Indian ships at 800 km. Well, I think that's too long of a range for us to detect and track ships at currently. However, I believe systems are being put into place for such a thing. I can assure you that the range of our missiles is not the limiting factor - it is the range at which we can give those missiles targeting data. But there is very strong indication that a sensor net is in the works - both for long-range submerged, surface, and air threats.
B. We need to hit land-based Brahmos sites - we have Baburs for that I think.