We have our production environment on EC2 classic, and we have a lease on some servers in a managed hosting environment. We would like to put a portion of our backend service in the data center, but there is no security built into the application yet, so we need to rely on private networks and VPN. I think this will be easier once we migrate to VPC as AWS already provides this kind of service, but we are not there yet.
Network Description
EC2 Classic puts all instances in 10.0.0.0/8. Our data center also has a subnet within that range, but I suspect we can change that. There are two routers at the data center that can connect an IPSEC VPN.
Service Description
The services running in the data center need to be able to initiate connections to services in EC2 and also receive connections initiated by services in EC2.
Ideas
I'm sure that if our services at the data center only needed to initiate connections to services in EC2, then it would just be a matter of setting up VPN endpoints in EC2 for the routers at the data center to connect to, use a different subnet in the data center, and finally, route all connections to 10.0.0.0/8 over the VPN.
For the other direction, is the best option to configure an extra route on all EC2 instances that need to initiate connections to services in the data center?
You need to put your instances inside an Amazon VPC, with what Amazon calls a "hardware connection" to your datacenter. There are two scenarios for this : http://docs.aws.amazon.com/AmazonVPC/latest/UserGuide/VPC_Scenarios.html I won't copy-paste what the document already says as it's pretty descriptive.
Scenario 3 and 4 are relevant to your use case.
For your specific questions
You may use 'Endian' or pfSense to create IPSec Site to Site VPNs. Both have small footprints and easy to configure with good documentation and even with video tutorials.
http://www.pfsense.org/
http://www.endian.com/