How can I create a friendship that must be approved with the Relation module?
Rules is just a handy "programmatic tool" (and API) to encapsulate things. Relation is a way to express -- well Relations.

In my opinion, using just relation and either Views or RelationQuery or EntityFieldQuery you can come up with what you need.

You just need more than 1 Relation.

Something like 1 relation of:
UserA &lt;- are_friends -> UserB

to express a global "friends list" of users within your site. You could make another relation a_user &lt;- has_friends -> user(s) which could be 1 users friends list.

Another relation:
UserA &lt;- is_a_friend_request -> UserB (1-way relationship)

The is_a_friend_request relation could have an attached field of 'request_status' which is a "select list" field type for instance with "approved" and "denied" or "ignore" as options.

A view could be made to show to any user of their "friend_requests". Acting on a friend request adds a recipient user to a given user's "are_friends" relationship.

I'm not sure if this is a naive way of looking at your problem ... you could definately use rules in there somewhere ... but its not a necessity.