yeh, good advice from bcf&gloves. the charter airlines are the best place to start. My Travel, First Choice, Thompson, Monarch etc. They are all accepting applications on their website (i believe) at the moment.
I also heard through the grapevine that virgin like to employ people with no experience, so they can mould you to the virgin way of thinking (i am only stating what I heard this may or may not be fact) so dont think that becuase you are new to this they wont want ya. makes you even more desirable i reckon!
good luck!