There are a few ways to achieve what you want. The first option is to use, as you mentioned the REST API. You will have a user in Salesforce that has administrative rights. The documentation on how to connect to an endpoint in Salesforce can be found here. I know some of the examples are not in PHP, mostly C# and Java but you could work out what it's trying to do.
Important
I recommend having a look at Bulk API and using it if you are
planning to perform operations on Salesforce's database.
Salesforce being a cloud application in a multi tenant environment you
need to be aware of the limits and you need to insert or upload
data in batches.
Second option will be to use Data Loader or a tool like DBamp, tools that by default use Bulk API, which connects from your database to Salesforce and then you can perform different updates, inserts using SQL statements which might be easier for you to start with.
You could also use SOAP API where you consume a WSDL and then perform operations to Salesforce. Here you can find documentation for SOAP API
There is also and I encourage you to look at, the Force.com PHP Toolkit which fulfills a lot of your requirements without you trying to re-develop.
Hope it helps and good luck!