As captioned, I need to send mailers to my 400,000 customer base.

I am thinking of a PHP program that sends mails to 1,000 users per minute, then flags them as “sent” and then the next minute only chooses 1000 customers who are “not sent yet”.

This way, it goes through all the customers in chunks of 100 at a time. In all, this program should therefore send all mails in 400 minutes.

Is this the best way of doing it? Will Exim be able to handle it from a dedicated mail server?

You can do it yourself, but just make sure you read up on how to configure your mail server AND DNS setting of your domain to avoid looking like a spammer.

Personally, I would outsource such a headache to a newsletter service like ConstantContact or similar. (Webserver is different). Exim server has 4GB memory, and does nothing except this.