Problem with definition of bisimilarity
You seem to be confusing the definition of bisimilarity with an algorithm for finding a bisimulation.

In your examples, the states are indeed bisimilar, and the relation is the set 
$$\{(A,A)\}$$
It is easy to verify that it satisfies the desired properties.

This means that the structures are indeed bisimilar.

What you were trying to do is to find an algorithm for constructing a bisimulation, given the two different structures. If you try to proceed by taking the initial states, and moving through paths, then you indeed encounter a problem with cycles. (By the way, if the structures were trees, or DAGs, then your approach would work).

This is why algorithms for finding bisimulations typically take a different approach -- namely refinement: you start with a naive relation (e.g., everybody is bisimilar to everybody), and whenever you find a mismatch, you refine your relation.

Take a look at the "fixpoint" definition of bisimilarity here, and try to extract an algorithm from it.