So Heroku routes their requests to your dynos randomly. While you're enhancing your middleware to log that dyno-level queue time, I have an optimization for you that should help fix the issue outright!
gem 'rack-timeout'
Rack::Timeout.timeout = 0.5
gem 'SystemTimer', :require => 'system_timer', :platforms => :ruby_18
gem 'rack-timeout'
Rack::Timeout.timeout = 0.5