gistfile1.rb

require 'nokogiri'
require 'net/http'
require 'open-uri'

GOOGLE_API_KEY = ''

states = ["Alabama",
          "Alaska",
          "Arizona",
          "Arkansas",
          "California",
          "Colorado",
          "Connecticut",
          "Delaware",
          "District of Columbia",
          "Florida",
          "Georgia",
          "Idaho",
          "Illinois",
          "Indiana",
          "Iowa",
          "Kansas",
          "Kentucky",
          "Louisiana",
          "Maine",
          "Maryland",
          "Massachusetts",
          "Michigan",
          "Minnesota",
          "Mississippi",
          "Missouri",
          "Montana",
          "Nebraska",
          "Nevada",
          "New Hampshire",
          "New Jersey",
          "New Mexico",
          "New York",
          "North Carolina",
          "North Dakota",
          "Ohio",
          "Oklahoma",
          "Oregon",
          "Pennsylvania",
          "Rhode Island",
          "South Carolina",
          "South Dakota",
          "Tennessee",
          "Texas",
          "Utah",
          "Vermont",
          "Virginia",
          "Washington",
          "West Virginia",
          "Wisconsin",
          "Wyoming"]

class GoogleMapsParser < Nokogiri::XML::SAX::Document
  attr_reader :eastern, :western
  attr_writer :state

  def initialize
    @wait = nil
    @state = nil
    @current = nil
    @most_east_val =-1000
    @most_west_val = 1000
    @eastern = nil
    @western = nil
    @state = nil
  end

  def start_element(name, attrs = [])
    case name
      when 'Placemark'
        @current = {}
      when 'coordinates'
        @wait = 'lonlat'
      when 'LocalityName'
        @wait = 'city'
      when 'PostalCodeNumber'
        @wait = 'zip'
      when 'CountryNameCode'
        @wait = 'country'
      else
        @wait = nil
    end
  end

  def characters(string)
    return if string[0] == '\n'
    if @wait
      @current[@wait] = string
      @wait = nil
    end
  end

  def end_element(name)
    if name == 'Placemark'
      if @current.delete('country') == 'US'
        lon, lat, _ = @current.delete('lonlat').split(',').map {|coor| coor.to_f}
        @current['state'] = @state
        @current['lon'] = lon.to_f
        @current['lat'] = lat.to_f

        if lon < @most_west_val
          @most_west_val = lon
          @western = @current
        end

        if lon > @most_east_val
          @most_east_val = lon
          @eastern = @current
        end
      end
      @current = nil
    end
  end
end

parser = GoogleMapsParser.new
http = Net::HTTP.new("maps.google.com")
states.each do |state|
  parser.state = state
  xml = http.request(Net::HTTP::Get.new(URI.encode("/maps/geo?q=#{state} Ruby Street&output=xml&key=#{GOOGLE_API_KEY}"))).body
  Nokogiri::XML::SAX::Parser.new(parser).parse(xml)
end
uri = URI.encode("/maps/api/directions/xml?origin=#{parser.eastern.delete('lat')},#{parser.eastern.delete('lon')}&destination=#{parser.western.delete('lat')},#{parser.western.delete('lon')}&sensor=false&key=#{GOOGLE_API_KEY}&alternatives=true")
puts uri
doc = Nokogiri::XML(xml = http.request(Net::HTTP::Get.new(uri)).body)
meters = 1_000_000_000
doc.xpath('//DirectionsResponse/route/leg/distance/value').each do |node|
  value = node.text.to_i
  meters = value if value < meters
end
puts parser.western
puts parser.eastern
puts meters

Seems like Google Maps returns different result when you use 1 http session :(, so my first answer was wrong.
Now I got:
{"city"=>"Anchorage", "zip"=>"99515", "state"=>"Alaska"}
{"city"=>"Orrington", "zip"=>"04474", "state"=>"Maine"}
7183777