What is the highest baud rate that can work between Android device and an Arduino connected to an HC05?
The HC-05 may only have implemented baud rates up to 1382400, even though the protocol is spec'd for up to 128000.
If you're using Software Serial to talk to the HC-05 from an Uno, 9600 baud is about as fast as SoftwareSerial can keep up with incoming bytes (I've heard from some people that 19200 will work).
If you're using one of the UARTs on a Mega, you may be able to use the full rate implemented by the HC-05. An experiment would be in order...
Update:

I did an experiment and found out that the maximum baud rate
achievable between the HC05 (communicated with by SoftwareSerial on
Arduino Nano) and the Android device is 115200.

I would guess you were transmitting from the Arduino? I've been able to transmit that fast with SoftwareSerial but its receiving ability is more limited. (This has enabled me to, f/ex, set an HC-05 or an ESP8266 to a slower baud-rate than it shipped with, by blindly transmitting an appropriate 'AT' command at the higher speed, then testing it at my intended speed to see if the command worked).