You can also run into the problem of the situation where the org is completely out of licenses. That happened to me recently. user320 is on the right track. What I had to do was query for an existing user
FROM USER WHERE Is_Active = True AND Profile.Name = 'CustomCompanyProfile'
Once you got the user returned from the query, as was pointed out by user320, you could easily clone it for your testing (multiple times if you needed more than one user). However, unless you have a way to do a schema query to get the required profile name you might need for a given org, I'm not certain you'll be able to do what you're asking for in every org. This doesn't even take Roles into account. In a recent situation for me, Roles didn't affect the trigger I was working on, so it was a moot point.
One suggestion I have would be to do the schema query, then grant the queried user the specific profile permissions required (or even all of them that exist) to ensure access your package. You could do the same for Roles as well. Before the class exits, simply undo any changes you've made to the existing user's profile, assuming you didn't make those changes to a clone; the latter of which would probably be the "safest" way to do what you're looking to accomplish since that user wouldn't persist once you exit the class.