Is there a way to make Geocode or location address based on a shapefile streets, without using a web service and using QGIS or some open source software?
You can install PostgreSQL (opensource) and the PostGIS and TIGER extensions to load the US TIGER data. This post has a lot of good info that I used to load the census data.
Then you can run SQL queries to get at the data or visualize it with QGIS.
I loaded all US Data into PostgreSQL on a Win 7 (64 bit) with 8 GB ram and a 230 GB hard-drive (with other apps installed).... I am just about of of space though with the US data taking up around 100 GB.
For other countries, you'll probably need to search and see what others are doing.
The MMQGIS Plugin has a 'Geocode from Street Layer' tool that you can use to geocode locations against your streets data.
You can point to a CSV file of locations you want to geocode.
Then you set the parameters of the geocoding - really setting the fields in your source data that contain the street segment attributes needed to geocode.