If you domain is at Windows 2003 functional level you can only have Windows 2003 domain controllers so this is fairly easy. I assume from the information given you only have a single domain. I also assume you are using AD integrated DNS
You don't say if you are using Windows 2008 or 2008 R2. I would recommend R2 if at all possible.
1. Upgrade the schema - need the schema master to do this. Remember R2 is 64bit only so you will need a 64bit machine to run this.
2 Install the new domain controllers as domain members. These two steps can be reversed if you need a 64 bit machine to run the schema upgarde.
3. Once the schema upgrade has replicated then promote the server to be a domain controller.
4. Repeat step 3 for as many domain controllers and locations as required.
5. DCpromo down the windows 2003 domain controllers, remove from domain and decommission/reuse
6. Raise domain/forest functional levels