I can't speak for other airlines, but at least with AA, as long as you are not one of the last 10 or so people to board, you will find overhead space. It may not be near your seat, but you won't be required to gate check. If you are really worried, call the airline and ask them what options they have for priority boarding. Most that I've dealt with have some sort of (relatively cheap) option to upgrade your boarding status.