OK, here's a suggestion for you: What about Prague? I've not been but lots of people say it's a great place (and cheap!).
Fly out from Newcastle at 1130 on Friday and back from Prague at 1505 on Sunday, with easyJet. The return fare is �144.48 each, including taxes and charges. That might not seem to leave much for two nights accommodation but there are plenty of cheap, central places available. For example, if you don't mind sharing a bathroom, you can stay at the Charles Bridge Guest House for �10.49 each per night. (i.e. the total for flights and accommodation would be �165.46 per person). For a little more luxury, with an en suite bathroom, you could stay at the Manhattan Guest House for �17.69 each per night. (i.e. your total for flights and accommodation would be �179.86 each).
Unlike some destinations, transfers from the airport won't cost a fortune. According to the airport website, the Airport Express service cost CZK45 (about �1.20), with all other bus and train services charged at a flat fee of CZK20 (about 50p):
http://www.csl.cz/en/site/klient/sluzby_kontak ty/doprava_na_letiste/do_mhd.htm
Book flights here:
http://www.easyjet.com/en/book/index.asp
Go here for accommodation:
http://www.hostelworld.com
(Click 'Additional search options' and select 'Guesthouses' and 'Budget Hotels').
Tourist information is here:
http://www.pis.cz/a/
Chris