First off all, before I get into, might I suggest a cut-over migration? They're a lot easier, a lot less work, and make sense when you only have one mail server. Downside is that there will be an email outage of however long it takes to get the data (mail) over from one server to the other (and then decommission the old server, and assign the new one to the old one's ip and hostname). You can generally make this outage last a few minutes at most, with the right tools, if you migrate the bulk of the email over before the cutover date, and do a diff on the data, so you're only effectively migrating a day or so worth of data, instead of all of it.
Having said that... no, you wouldn't need a public IP for your new server, because you'd set up the current/old server to forward mail to it instead. (See below.)
Typically, in co-existence migrations, you set up one mail server to forward mail to the other (if you only have 2). The easiest way to do this would be to set up [fake] subdomains, assign one to one mail server, the other to the other mail server and configure a smarthost to handle mail routing from one to the other. You'd leave your Exchange 2003 server as it is, and not set up a public IP or NAT for the 2010 server.
So, let's use oldmail.company.com and newmail.company.com as subdomains (to keep things simple for the example, you probably don't want to use those actual names). The oldmail subdomain would be "assigned" to the Exchange 2003 server (internally, through the Exchange System Manager, not through DNS) and added into the list of mail domains on which that server is authoritative, and the newmail subdomain would be added to the list of domains on which the 2010 server is authoritative. You would then configure the smart host settings on both servers to check the other mail server if a recipient isn't found locally, and set up send and receive connectors to handle mail forwarding from one server to the other. (So that your Exchange 2003 server will forward any mail for [recipient]@newmail.company.com to the 2010 server and the 2010 server will forward any mail for [recipient]@noldail.company.com to the 2003 server.)
In this way, users on both mail servers can send to each other internally (each mail server checks the other to see if a recipient is valid before rejecting an email), and external users can too. Mail would arrive at the 2003 server as before, and if the recipient isn't found, it would check with the 2010 server to see if your recipient is over there. Once everyone's over onto the Exchange 2010 server, you'd schedule a time to shut off the Exchange 2003 server, put the 2010 into its place, and remove the smarthost and mail routing rules. This, of course, assumes that you correctly setup the 2010 mail server, and it's set up to receive mail for external, as well as having company.com as one of its mail domains.
The three main drawbacks of this are:
You have to handle the users manually - each user can only have one account, so you need to remove them from the old server once you've migrated them to the new one.
You have to handle user mail client settings - when they migrate over to the new server, they have to point their clients at it, and then point them back at the original location once you cut over. (Also, calendaring and your other "not mail" features of the mail clients tend to be a pain to get quite right during the co-existence).
Emails sent from one server or the other will show as [sender]@[subdomain].company.com instead of [sender]@company.com unless you jump through hoops to change that. When the co-existence is done and one or both subdomains are removed from your mail server, that will cause replies to those old emails to bounce, and probably more help desk calls than you'd like from technically illiterate users and clients.