1. Make contact with Terrorist groups who have internet access
2. Prove abilities to that group by: (a) taking out a computer target with a virus or other cyber attack like stuxnet, (b) cracking some encryption and delivering classified information, (c) threatening them with exposure or destruction
3. Barter further information and/or attacks for favors such as building hardware, obtaining weapons, etc. until the AI can threaten nations either on its own or disguised behind the Terrorist group

This basic pattern would probably work for a lot of different groups or individuals besides just Terrorist groups. The general formula is:

1. Identify a person or group that is willing to "deal with the devil" to get what it wants
2. Prove your power to them while not giving them everything right away
3. Use them as pawns in your master plan.

Just complete the story: Give an electrical engineer with a gambling problem a means to make money to get out of debt to his loan sharks and protect his family Blackmail a politician with a dirty secret Give a loner computer geek companionship and dark-arts social tips Give a morally ambiguous PHD candidate a thesis Impersonate a deity to a cult or religious group Sell information to a rogue nation-state

This could even be a distributed plan so no one group is indispensable and no one group could possibly determine what these seemingly random favors are building towards.

Given the relative lack of restrictions on the hypothetical, we can actually draw inspiration from fiction here. Tom Riddle's diary, the demon in the computer from the first season of Buffy, etc.