OK. So, I tried the SDFat lib. This library is definitely better than the default SD library that comes with adruino.
But that is not how I solved my problem of low data-rate.
I followed the instruction of the author of SDFat library from this post.
According to fat16lib, to increase the data rate we need to use flush() wisely. We would want to write() the data in each cycle, but we only need to flush() once every 100 cycles or so depending on how much data is being written in each cycle. Also, be sure to keep the flag in SD.open() as 'O_WRITE | O_CREAT' instead of 'FILE_WRITE'.
This sure increased the speed by a great factor. But I needed more!
Storing the data in binary (check out this blog) improved the performance even more.
My current speed is approximately 100-120 KBps (that's kilo bytes) with a class 4 SD card!
Finally, I want to thank you guys for your help.