(Adds Biden call with Yanukovich, Polish official, U.S. lawmaker, paragraphs 4-8)
* EU ministers hold "difficult night" of talks
* Road map for peace still elusive
* Death toll in two days violence reaches 75
* Biden tells Yanukovich U.S. prepared to levy sanctions
By Richard Balmforth and Alessandra Prentice
KIEV, Feb 21 (Reuters) - European Union ministers sought to broker a political settlement in Ukraine after gun battles between police and anti-government protesters brought the death toll to 75 in two days of the worst violence in the country since Soviet times.
Three hours of fierce fighting in Kiev's Independence Square, which was recaptured by the protesters, left the bodies of over 20 civilians strewn on the ground, a short distance from where President Viktor Yanukovich was meeting the EU delegation.
The ministers, from Germany, France and Poland, embarked on "a night of difficult negotiations" with Yanukovich and the opposition, said EU officials, who hoped a plan for an interim government and early elections could bring peace.
"Talks of Polish, German, French foreign ministers at Yanukovich's office still going on. The opposition leaders, the parliament's speaker, many MPs attend," spokesman Marcin Wojciechowski, who is in Kiev with Polish Foreign Minister Radoslaw Sikorski, wrote in a Twitter post.
U.S. Vice President Joe Biden told Yanukovich in a phone call on Thursday the United States was prepared to sanction officials responsible for violence against civilian protesters. It was the call between the two men since violent protests erupted in Kiev.
"He called upon President Yanukovich to immediately pull back all security forces - police, snipers, military and paramilitary units, and irregular forces," the White House said in a statement, adding that Biden made clear "the United States is prepared to sanction those officials responsible for the violence."
The Obama administration is considering a range of sanctions, the White House said on Thursday, although it did not give details on what options were being considered or the timeline for decisions.
U.S lawmakers are planning legislation to reinforce any administration action, Senate Foreign Relations Committee Chairman Robert Menendez said in a statement late on Thursday.
France's foreign minister said there was still no agreement over a proposed road map to ease the crisis, which erupted in November after Yanukovich abandoned a proposed trade deal with the European Union and turned instead towards Moscow.
"There is no agreement for now, the negotiations are very difficult and we are working to reach a peaceful solution," France's Laurent Fabius told reporters.
The three ministers, who extended their stay in Kiev until Friday, have been negotiating with the government and opposition since Thursday morning.
"We have to find every way to see how we can put a new government in place, think about elections and see how we can end the violence, but at this moment there is no solution," Fabius said.
Earlier in the day, riot police were captured on video shooting from a rooftop at demonstrators in the central plaza, known as the Maidan. Protesters hurled petrol bombs and paving stones to drive the security forces off a corner of the square the police had captured in battles that began two days earlier.
The Health Ministry said 75 people had been killed since Tuesday afternoon, which meant at least 47 died in Thursday's clashes. That was by far the worst violence since Ukraine emerged from the crumbling Soviet Union 22 years ago.
The trio of visiting foreign ministers met Yanukovich and the opposition after EU colleagues in Brussels imposed targeted sanctions on Ukraine and threatened more if the authorities failed to restore calm.
Vitaly Klitschko, an opposition leader, said he hoped for a deal overnight, but added there was no clear result so far.
In further diplomatic efforts, U.S. President Barack Obama spoke to German Chancellor Angela Merkel, who in turn discussed Ukraine with Russian President Vladimir Putin.
Putin "stressed the critical importance of an immediate end to bloodshed, the need to take urgent measures to stabilise the situation and suppress extremist and terrorist attacks" the Kremlin said - sharing Yanukovich's view that he faces a coup.
The White House said Obama and Merkel agreed it was "critical" U.S. and EU leaders "stay in close touch in the days ahead on steps we can take to support an end to the violence and a political solution that is in the best interests of the Ukrainian people". Earlier this month, bugged and leaked diplomatic phone calls exposed EU-U.S. disagreement on Ukraine.
The EU plan "offers a chance to bring an end to violence," Polish Prime Minister Donald Tusk said in Warsaw, adding Yanukovich was willing to hold rapid elections to parliament and the presidency - the latter something Yanukovich has so far appeared reluctant to consider, a year before his term ends.
Tusk also spoke by phone with Biden about the crisis.
In Kiev, demonstrators on Independence Square held a vigil after dark for fallen comrades, lit by mobile phone screens held aloft.
Medics carried bodies on stretchers through lines of protesters who chanted, "Heroes, heroes" to the dead.
Although armed militants on the barricades tend to be from the far-right fringe, the opposition has broad support. But many Ukrainians also fear violence slipping out of control.
"This is brother fighting brother," said Iryna, a local woman walking to Independence Square to donate syringes for blood transfusions. "We need to realise we're all one people."
Kiev residents emptied bank machines of cash and stockpiled groceries, with many staying off the streets.
In a sign of faltering support for Yanukovich, his hand-picked head of Kiev's city administration quit the ruling party in protest at bloodshed.
In an indication that Yanukovich is losing support in parliament, the assembly late on Thursday adopted a resolution urging authorities to stop shooting, withdraw police from the centre of Kiev and end the action against the protesters.
But core loyalists were still talking tough.
Interior Minister Vitaly Zakharchenko, wearing camouflage as he made a televised statement, said police had been issued combat weapons and would use them "in accordance with the law" to defend themselves - or to free 67 of their colleagues his ministry said were being held captive.
Demonstrators said captured police had been allowed to go.
(Additional reporting by Natalya Zinets, Pavel Polityuk, Vasily Fedosenko and Sabine Siebold in Kiev, John Irish in Paris, Francesco Guarascio and Adrian Croft in Brussels, and Roberta Rampton and Patricia Zengerle in Washington; Editing by Giles Elgood and Peter Cooney)