I agree with mdenil. If you need to traverse the network between each and every address, Network Analyst is the only way to go. It can solve for various conditions such as shortest distance or shortest time of travel based on speed limits and road classification, and take into account barriers, turn restrictions and other factors.
If you only want distances between addresses that fall along the same road, you could use Linear Referencing tools to build Routes based on the Road Names with the Create Routes tool. Then you could use the Locate Features Along Route tool to get the Route ID and measures assigned to your address points (assuming they are basically geocoded along the roads already). Then you could make a copy of that feature class and use the Make Query Table tool in the Data Management group to find create a cross link of all addresses that share the same Route ID and export that result. Finally calculate a new field that takes the absolute value of the difference between the measures from your origin address to your destination address.