How many partitions should I make and what formatting schemes should be used on those partitions? I am thinking of buying a 2 TB WD My Passport Ultra External Hard drive and I'll be using it with both OS X and Windows. I am planning to use this drive for my Time Machine data backup after creating additional partitions in the external HD. I will also be storing a large number of files of Music, Videos, VMs(>4GB) and software setups.

I know the limitations of Fat32 that it can't be used to copy files that are greater than 4 GB and of exFAT that it is prone to data corruption and chkdsk errors. I am confused on how many partitions should I make and what should be the formatting scheme on each partition? Also I want to know how much space should I leave on external HD for Time Machine Backup? I'll be backing up data only after a month or two, and my MacBook Pro has 256 GB SSD out of which around 220 GB is in use.
According to this article you can get OS X to read and write to NTFS, so if you are planning on using the disk for both, then go with NTFS. The one thing you need to check is if Time Machine will write to NTFS. It writes to NAS's which are not using an Apple proprietary file system, so it may work okay, just check before you commit to it.

As for partitions, the way Time Machine works is that it lays down an initial backup and then does incremental backups so that you can do things like go back in history and recover an accidentally deleted file as well as restore a Mac completely. It gives you each backup point in the most recent month, then it makes one month archives back for as much space as you give it. It starts to delete old archives when it runs out of space. You could probably get by with a 500GB partition for you 250GB SSD. You may want to consider 750GB if the go back to previous versions option sounds important to you. If not, go with the smaller partition and then you can have more room on the other partition for media archiving.

I am going to add a word of caution. In my personal experience, external USB HDD's are extremely unreliable. Almost every one that I have purchased, especially Western Digital Passports have bricked on me. I have lost data as I was doing the same thing you were doing and was extending my storage. I learned better.

Your best bet if you have a router is to get a two disk NAS that you can set up via ethernet. Internal Drives, especially HGST tend to be far more reliable than their external cousins. Two disk NAS from Synology is reasonably priced, easy to set up, and will give you the added benefit of being able to set it up as a RAID, which provides an added level of protection in that if one drive goes bad, you can always swap in a new drive and have the RAID rebuilt. RAIDs are not fool-proof, so you want to make sure you have a back up of this as well. Here you can take a gamble with an external USB HDD as your data is on the more reliable NAS.