Update:
DirectD at Federal Highway can replace the battery for you within 1 hour. Call them and check if they have stock, if they don't have stock you need to first go to DirectD and put in a deposit (~RM10), they will call you once they get the battery (they called me 1 day later in my case). Then go to DirectD with your phone and they will replace it for you in 1 hour.

Total cost: RM150 (if I remember correctly)

One thing though - the battery almost never charges to 100%, normally I see that it goes up to about 95% but it still lasts almost 1 full day so it's fine I guess.