So I'm a beginner in German and I'm trying to make my speech sound a bit more natural and I was wondering what interjections I might use at the start of a sentence like "Well, ..." or "So, ..." in English?
This is a very broad topic.
To start with how you started your actual question ("So I'm a beginner..."): This rather impolite and careless style of speaking is popular in German as well, especially amongst youth. A typical phrase is:
Also ich hab da mal ne Frage: ...
But this is really bad style. You should not turn to other people using that formula (unless you know really well what you are doing, e.g. you use this in an ironic way at a place where irony would be appreciated; or you want to signal to your audience "I am 15 years old and nobody has told me how to behave".)
Other examples for starter-interjections (with varying intensity of impoliteness or lack of behaving):
He [Ey], kannste mir mal das Glas da geben?
(Calling for somebody's attention)
Hm [Äh, Ähm, Öh, Öhm]. Ich weiß nicht recht.
(Signalizing a thought process)
Tja. Das war wohl nichts.
Puh [Uff], das war aber knapp.
Na, das ist aber komisch.
(Signalizing slightly being puzzled or staggered)
Zifix*, was soll denn das?
Würg! Was für ein Wetter wieder!
Mann [Menno], können die das nicht rechtzeitig liefern?
(Signalizing anger or aggressive disappointment)
Nu, was steht an?
(Introducing a question)
Boah! Was für ne Karambolage!
(Expressing amazement, often vis à vis something negative, or something overwhelming)
Wow! Was für ein Glück!
(Expressing amazement vis à vis something positive)
Umpf, das hätte jetzt nicht passieren dürfen!
(Expressing fright or dismay)
Huch, eine Spinne!
(Expressing slight fright, or surprise combined with slight fright)
Eieiei. Das ging daneben.
(Expressing slight fright, possibly combined with appologizing)
Eieiei, I think this is going to become quite a long list...
*) "Zifix" is short for "Kruzifix", a word used for civilized forms of cursing (perhaps only in regions that are catholic by tradition)