My need is a heavy use of routing. same as Google's Directions API. I'm looking for a viable alternative to abusing google and paying them too much.
how difficult is it to have my own server for that task?
It's possible but performance isn't going to be anywhere near what you'd expect from google api on a small budget for an entire country. You should try it and report back :)
ArcGIS Server and Network Analyst is out of the question given the budget. So go with Postgresql, PostGIS and pgRouting.
Not exactly an answer, but have you seen The Open Source Routing Machine (OSRM)
Their routing engine works on OSM-data it seems, but it is opensource, so it could provide som pointers. And their implementation is FAST: http://map.project-osrm.org/