theme or plugin or server is outputting html before the init hook fires, how is it possible to prevent this

Hook into 'plugins_loaded', that should be early enough. Theme output cannot be sent at this stage, so you should be safe – if you really just need the user agent.