Have a look at S3-Curl. It's a python wrapper that handles AWS keys and headers to properly generate the write CURL commands for the REST API for various amazon services (S3 included).
You could look inside the source of the .pl file to get an idea of how to create the curl requests yourself (only if you don't want to use s3-curl and have a restriction that you can only use curl directly).
You could use this in combination with Amazon's STS to generate a temporary token granting access for that particular upload. In this case, your modified flow would be:
- Initial request to domain.com/apikey/upload with parameters such as the bucket name, key for the uploaded file.
- Return a response with temporary credentials (through STS) only permitting upload of that particular file
- Use either S3 curl or curl and the temporary credentials to upload directly to S3.