I think what you want is to see whether this person is trustworthy and safe to be around. I question the assumption that a criminal background check will tell you that, for a few reasons:
- An official background check will only potentially tell you about a few specific kinds of negative behavior, leaving out lots of things that could actually be important to your decision to travel with them. For example, someone might be petty, rude, manipulative, and a liar, but that may never result in anything official on their record.
- Background checks only show stuff that people got caught doing. Just because someone has a clean background check doesn't mean he or she isn't a thief, batterer, drug user, rapist, etc. For something like rape, estimates indicate that only a tiny minority of cases ever result in an arrest, let alone a conviction. All of those unreported cases end up on no one's record at all.
- Related to the previous point, who gets caught doing what (and therefore, what makes it onto our official records) is subject to a range of complex issues including institutional bias (here's a link on well-documented racial bias in drug arrests and charges). By relying on these records, you may inadvertently replicate those biases in your search for a traveling companion.
Moreover, as you suggest in your question, asking for a background check has the potential to cause offense or scare people away. Personally, I know my record is completely clean --- if a stranger I met on the internet (and that's indeed what you are to them, as much as they are to you) asked me for information to conduct a background check, it would raise all kinds of red flags. Imagine how much more intense the negative reaction might be for someone who feels they have something they definitely don't want to share (maybe their mom is undocumented, maybe they got caught up in a bad situation when they were a kid and some judge decided to make an example of them, etc.). To answer your question directly, I think it is "too much" to ask someone to submit to a background check in this scenario. Moreover, I expect conducting those background checks would be mostly a waste of time and money for you anyway.
Instead, I recommend you attempt the old fashioned "getting to know you" approach. :) Invite them to tell you about themselves, their habits/likes/dislikes, favorite travel memories, whatever. And you reciprocate. Write back and forth a few times. If you're close enough, ask to meet in person to chat, or maybe plan a phone call or video chat. Ask questions, get to know them. Swap social media details with them, so you can check out their facebook/twitter/instagram/linkedin/whatever and they can do likewise.
During this process, you will be able to check up on plenty of the details they offer, to reassure yourself. A google search for their full name is likely to pull up any news articles featuring them. If they've told you, for example, cities they've lived in, places they've worked or studied, etc. you can add those terms to your googling to pull up more relevant results. Many court records are also freely available online (try googling "court records" and your state, or the state your potential travel companion lives in).
And, of course, you'll want to practice some good common sense: Whether or not you have a background check and/or you've been pen pals for ages, you should still put some extra protections in place and plan an exit should you need it. Have a phone that will get signal throughout your trip, and make sure other people know when to expect you at different points throughout your journey. Ideally, have another friend accompany you and your traveling companion at the beginning of the trip; if things don't feel right, you can bail when your friend does. I hope you have a great trip!
