No problem with the Arduino being behind a router.
You can either use port forwarding (which is what PaulS is referring to); that's where you specific a port on the WAN (internet) side, and forward it to a port on the LAN (internal network side) along with the internal network address of the Arduino.
Say your Arduino is on IP address 192.168.1.5 and is configured to listen on port 85. If you then program the router to forward requests on port 1000 to port 85, your remote server will send its request to port 1000 on your external IP address. Your router will know to forward the request to internal address 192.168.1.5 and port 85 (expressed as 192.168.1.5:85).
The reply from the Ardunio (you might want it to confirm back to the server that it received the data OK) will be routed back to the server.
There are two issues to consider. Firstly, asking users to program routers might be tricky unless they know how to operate them. I don't know which country you're in but some ISP's control home router configuration themselves to a point, which makes user configuration more difficult.
Secondly, the majority of home users have dynamic IP addresses; that is, the address of their router on the internet will not always be the same - and you'll need to tell your server the IP address it'll use to access each Arduino. If these change, and you have many of them, you need a way of telling the server what the Arduino IP addresses are. There's a neat solution to this though. Program your Arduinos to periodically 'announce' themselves to the server, maybe once a day. It's then trivial to identify the IP address the Arduinos are at; your server could update its database and consider any Arduino that hasn't announced itself for more than, say, 24 hours, to be 'offline' and not attempt to contact it until it has.
Alternatively, if the user who updates a record in the database is going to be at the same location as each Arduino, you could identify the address then. It's not clear if you'll have 1000 users, each with an Arduino (in which case, that would work) or a few users updating all the Arduino's in the network.
The router/firewall programming is your most likely issue. From a networking and IP perspective, what you are describing is perfectly possible.