If your road network is divided by segments, dissolve the buffers based on road name or some common attribute so that individual segments of roads do not count as two separate roads in the next step.
Buffer your street centerlines by a standard amount - more than half the typical ROW width, but no so large that it would overlap parcels that do not front on it. You may want to choose different buffers for different classes of roads. When you buffer, don't merge the polygons.
Spatially join the parcels to the road buffers, choosing "one to many". The "count" field on the results should allow you to identify all parcels with two frontages.
Now you have a table with rows for every overlap between a parcel and a road. You could easily summarize this to find all parcels overlapping two or more roads using either GIS or a database. But eliminating corner lots will be more tricky. Here's one broad method:
Set up topology for the buffer layer with a rule "must not intersect".
Export all errors to a new feature class of intersections.
Spatial join the intersections to the buffer layer, choosing "one to many".
At this point you have two tables: one with all frontages and one with all intersections between roads. It won't be easy, but you can write a SQL query that selects finds all parcels that have two frontages where those frontages do not intersect. The results would be the set of all parcels that have multiple frontages that do not intersect.
One advantage of this method is that it avoids choosing parcels with edges that are not on roads, such as where a parcel is adjacent to an alley, a water features, a railroad ROW, etc. A disadvantage is that the buffering won't be perfect, and you'll still have to visually check it for errors.
I'm not sure how to write the SQL - perhaps someone else can chime in on that.
Edit Thoughts on the SQL:
It would be fairly simple to solve for parcels with two frontages as below. Then you might need to manually look at parcels with more than two frontages, but hopefully there would be few, and most would be corner lots anyway.
This might work for selecting only non-corner parcels with two frontages:
select ParcelID from parcels
where parcelID not in (
((select Parcels1.parcelID, intersections.intersectionID from
intersections left join
(Select first(RoadID) as Road1, last(RoadID) as Road2, count(*) as frontages, ParcelID
from Parcels
where count(*) = 2
group by ParcelID) as Parcels1
on intersections.RoadID = Parcels1.Road1) as int1
inner join
(select Parcels2.parcelID, intersections.intersectionID from
intersections left join
(Select first(RoadID) as Road1, last(RoadID) as Road2, count(*) as frontages, ParcelID
from Parcels
where count(*) = 2
group by ParcelID) as Parcels2
on intersections.RoadID = Parcels2.Road2) as int2
on int1.intersectionID on int2.intersectionID))
Are there bad geometries involved? This sounds like a problem ESRI has when invalid geometries are used.. selef intersecting, incorrect ring orientation make it hard for the tool to work. In ESRI I use 'repair geometry', there may be something similar in QGIS to clean up bad data before intersect.
Here's a link to someone who has fixed geometries in QGIS http://faunaliagis.wordpress.com/2013/08/14/bad-bad-polygon-fixing-invalid-geometries-with-quantum-gis/ having not done it myself I can't comment on the effectiveness of their methods.
I looked at the images presented in the comments but, sadly, I am unable to decipher any of the meaning due to language differences.
Best Answer
I discovered a page named Constructing polygons from the shapes of other features on Esri's site that should allow you to contruct polygons from your lines with only an ArcEditor/Standard license. You can select the lines you want to convert to polygons, then use the Construct Polygons button on the Topology toolbar (ArcGIS 10.0 or earlier) or the Advanced Editing toolbar (ArcGIS 10.1 or later).
If only you had an ArcInfo/Advanced license, you'd be able to use the Feature to Polygon tool that does exactly what you want.