If regime change were to happen in Iran, effectively solving the second problem by bringing the reformist faction to power in Iran, the first problem would be solved because reformists would likely see reason and abandon the nuclear program in exchange for better international relations. Unfortunately, that isn't going to happen.
We certainly cannot force regime change through military action. After our performance in Iraq, the Iranians probably wouldn't trust us, regardless of the fact that we don't have the resources to do so anyway.
We cannot do it through covert action. We were responsible for an Iranian coup d'etat in the 50's, and ever since Iranians have have held to a paranoid fear of American covert action that has kept the CIA out of Iran.
That leaves reform within the system, but that's already failed as well. The hardliner system that keeps hardliners winning the President and Majile elections was overwhelmed once, in the 1996 election of reformist Khatami, when the popular vote so favored this obscure candidate that the harldiners let him win fearing a revolution. He proceeded to make some cautious reforms and reach out to America, but the hardliners fought back, using thuggery to intimidate reformists, the still harldiner Majiles to censor them, and even going so far as to assassinate prominent reformists. In 1999 the conflict peaked, when students took the streets in protest to a new law that would ban most reformist newspapers. The hizbollah and other hardliner thug groups showed up to beat the students into submission, but the students fought back. The riots escalated, and students went so far as to make statements denouncing not just the law, but the entire government. They were ready for a revolution. Unfortunately, Khatami was not. Faced with preparations for a violent hardliner reprisal (military units were being moved into position near rioting cities), he caved, denouncing the riots. The hardliners had regained control, and by his 2000 re-eleciton, Khatami was nothing more than a puppet President without any real power. Since their brush with revolution, the hardliners have consolidated their position, liberalizing the economy like China and social restrictions to vent the rage of Iran's youthful population. Additionally, with oil prices at record highs, there's no reason to believe the Iranian government cannot deliver economically most everything their populace wants, effectively bribing their populace into submission.
Thus military action will not work, covert action won't do the trick, and a spontaneous revolution is not going to happen until the price of oil goes down, and probably a while after that. We can improve conditions for regime change keeping pressure on the current regime through embargoes and harsh diplomatic statements, perhaps also work to increase our covert action capabilities in Iran, but not much more. Regime change is something to hope for, and we should support such a goal, but its nothing we can count on toward solving more short-term problems with Iran.