With a bit of Python coding you should be able to do it.
To create point features from your lines' vertices without an Advanced Licence, you need to iterate the feature parts of each line and write the points to a different feature class. There is an example how to do this here (Read polyline geometry) and write to the new feature class with the Insert Cursor. For your situation where the vertices might be far apart, you probably need to break the line features up into equal length smaller segments - for this you can use the positionAlongLine method (find usage instructions on this page) in an iteration to determine how far along the line the point should be.
Once you have your segmented feature points for each line (in different feature classes), you can check which two points from each line points feature class are the closest to one another, take the geometric centre of them and create an array of these points to create a line feature again.
You can try this code to create the centre line points:
import arcpy
# point layers loaded in your dataframe
pnts1 = arcpy.mapping.Layer("line1_pnts")
pnts2 = arcpy.mapping.Layer("line2_pnts")
# create search cursor to iterate through first layer
scur = arcpy.SearchCursor(pnts1)
row = scur.next()
closestPnt = 0
closestPntID = 0
cenPnts = []
ctr=0
while row:
shp = row.shape
geom = shp.getPart()
print "Geom1 - " + str(row.FID) + ": " + str(geom.X) + ":" + str(geom.Y)
mindist = 9999
tmpdist = 9999
# search cursor for feature in second line point layer
scur2 = arcpy.SearchCursor(pnts2)
row2 = scur2.next()
geom2X = 0
geom2Y = 0
while row2:
shp2 = row2.shape
geom2 = shp2.getPart()
# check distance between points first and second layer and find closest point
tmpdist = shp.distanceTo(shp2)
if tmpdist < mindist:
mindist = tmpdist
closestPnt = shp2
closesPntID = row2.FID
geom2X = geom2.X
geom2Y = geom2.Y
row2 = scur2.next()
del scur2
print "Geom2 - " + str(closesPntID) + ": " + str(closestPnt.getPart().X) + ":" + str(closestPnt.getPart().Y)
print "Dist: " + str(mindist)
if shp != closestPnt:
# calculate geometric centre of two points closest to each other
cenX = (geom.X + geom2X) / 2
cenY = (geom.Y + geom2Y) / 2
midpnt = arcpy.Point(cenX, cenY)
# create mid line point
ptGeometry = arcpy.PointGeometry(point)
print "Mid1 >> " + str(cenX) + ":" + str(cenY)
# add point to array
cenPnts.append(midpnt)
row = scur.next()
ctr += 1
del scur
# write list of points to new point feature class ("cenlinepnts" - create point feature class and load into dataframe) for centre line
inscur = arcpy.InsertCursor("cenlinepnts")
insrow = inscur.newRow()
for p in cenPnts:
insrow.shape = p
inscur.insertRow(insrow)
del inscur
There might be more efficient ways, but for this you don't need an Advanced licence.