Migrating Exch 2010 to 2010

It's not really a migration.   Just install your new Exchange 2010 server, create the databases and move your users to the new databases.

The best thing to do is keep your new Exchange server at the same SP/RU level as your current one.  Once things are moved over, decommission the old server by performing an uninstall and then update your new server.  I see that your current Exchange server is confused as to where it is in patch level.  Get it as close as you can and move everybody off as quickly as possible.

http://exchangeserverpro.com/move-mailboxes-exchange-server-2010/

https://www.youtube.com/watch?v=ffbH0Bvdxkk

Does the new exchange install need to match my current servers build number?

in this case, no, but it should be at the latest release (SP3 with update rollup 10)

Microsoft Exchange Server 2010 Service Pack 3 (SP3)
http://www.microsoft.com/en-us/download/details.aspx?id=36768

Update Rollup 10 For Exchange 2010 SP3 (KB3049853)
http://www.microsoft.com/en-us/download/details.aspx?id=47676

Can this be done with new server concurrent to minimize downtime?

yes, the new server can be built while the current one is running

Can someone please help with this and provide me with some detailed instructions on the best way to handle this situation?

have not done this myself, but once your server is built, need to migrate mailboxes and public folders over, change your mail routing (depends on what you have for send connectors, etc.) to use the new server, and check your web services (OWA, outlook anywhere, etc.) to make sure the URLs point to the new server

hopefully this can get you started
oh, and i'm assuming the old server has all of the roles (mailbox, transport, cas)?

h, and i'm assuming the old server has all of the roles (mailbox, transport, cas)?

Sorry forgot to mention its a single server scenario with all roles.

It appears I am getting conflicting responses if the  new and old server need to match or closely match SP and RU.  

I failed to mention that the new server is 2012, so it looks like I will need SP3 for exchange to function?

Thanks for the comments guys! This will get me started and I will let you know if I have any questions.