Finally done. The iPhone Dev Team has released redsn0w 0.9.14b1 which allows us now downgrade from baseband 06.15.00 (or the iPad baseband) to baseband 05.13.04.
Download original iOS 4.2.1 firmware
Build a custom firmware using Pwnage Tool or Sn0wbreeze. Steps are very easy and you are guided by the software itself.
Use iTunes to restore to the custom firmware built. Use Alt + "Restore" button on Mac OS X and Shift + "Restore" button on Windows to point to the custom firmware created in the previous step.
Open redsn0w. Click on Extras.
Click on Select IPSW.
Point to the 'original' IPSW downloaded from the internet (NOT the custom built firmware)
Click Back. Click Jailbreak.
Check Install Cydia and Downgrade from iPad baseband.
Follow the steps as directed.
After the process completes, you should find that your phone is on baseband 05.13.04.
It's that easy. In case not, do feel free to leave a comment.