A few other things that might be important to know are:
1. Have you asked the teams? If so, what did they say?
2. What is your role on the team?
3. How big is each team that you're talking about?
4. Are your teams co-located or distributed?
5. Is the PO the same person on both teams?
6. How would you describe the Scrum maturity of your teams?
7. Do you do all other Scrum practices(besides cross functional teams)? If not, which ones do you currently not do?
Some of the answers to these questions might lead me to suggest other ideas.
Here is an idea that ignores the above questions, but if I had the answers to the above questions, my advice might change dramatically, so reader beware. :-)
1. This is why feature teams are better. I don't necessarily agree with the Dynamic Feature Team concept,but you can certainly begin building feature teams in an incremental way, with the goal of eventually achieving a cross functional, feature team. See Cohn's Succeeding With Agile...
for more good info on feature teams vs. component teams. This(not having fully cross functional teams) should be considered a fairly high priority impediment.
2. If at all possible, I'd recommend getting a good Scrum coach because problems like these are not easily solved by practitioners. It sounds like you could use a good re-org of your teams into specific feature and component teams in the short term, then move to full on feature teams in the longer term. Often a coach can help in this arena tremendously. Keep in mind that this statement of mine is self serving in that I'm a professional Scrum coach. :-)
3. Now, if #1 and #2 is just not possible at all, I consider this to be a problem of "external dependencies" between Scrum teams. In your situation, which is complex to convey over the internet using text, I think I would approach it this way:
The back end team is a "component team." The API team is a "feature team". Someone from the API team is either the PO or a *very* key stakeholder involved in the backend team.
It sounds like the dependency really only goes one way. The API team depends on the back end team. So, the back end team has one Story whose title is something like "Add option to block web crawler." They consult with their PO and key stakeholders(the API team, among possibly others) as to how to define the *interface* between the API layer and the "back end layer." -- in other words, the "what". The backend team finishes the story and demonstrates the functionality at a Sprint Review, where our API team PO or key stakeholder is present(as well as anyone else from the API team who wants to attend).
The API team now implements the story you speak of and performs end to end testing, and demonstrates that feature to it's key stakeholders(presumably the backend team is not a key stakeholder here on this story).
That is how you coordinate a story using what I call "the sequential method".
You can also do the "parallel method" like you described, where both teams take it on at the same time. I only tend to favor the "parallel" method when I'm 95+% confident that both teams can finish their piece in the same sprint, and where both teams have a strong history of tight and happy collaboration.