What can I do to make this work?

Method

The way I'd go about doing this, would be to create a function that creates a new table, with all the same keys and values to the original song list. You could just randomize the order of the initial song list, though if you plan to use it for anything else and the order matters, you're going to want to create a new table for it.

This is also a great opportunity to take advantage of the wait method you can call on events, to suspend the thread until being resumed again. We can use this method on the Ended event of the Sound object, and it's very well compact. I'll go over all of this in the explanation below.

Starting off

First, let's add the variables and create the function:

local Songs = {309109778,304029790,243372213,417500483,281929968}
local Speaker = workspace:WaitForChild("Sound") -- I'd recommend using WaitForChild for this.

-- We'll call the function 'PlayRandomSounds'
local function PlayRandomSounds()

end

Next, we need to create a copy of the table (just like you did with your "Queue" table). This will allow us to select and remove random elements from the table, without effecting the original one:

-- Assuming everything from above is still defined
local function PlayRandomSounds()

    -- Private copy of "Songs"
    local Songs = {unpack(Songs)}

end

Now for choosing random songs, we're going to use a for loop to iterate the copy of the table we just made. As the loop is traversing through the table, it will select random elements along with removing them (to prevent selecting the same random song twice).

-- Assuming everything from above is still defined
local function PlayRandomSounds()
    local Songs = {unpack(Songs)}

    -- Iterate the copied table
    for i = 1,#Songs do

        -- Get, while also removing the randomly selected element
        -- since table.remove returns the element it removed, and we
        -- are indeed working with arrays, this is valid.
        local selected = table.remove(Songs,math.random(#Songs))

        -- Set the SoundId and play it
        Speaker.SoundId = selected
        Speaker:Play()

        -- And finally, use the wait method for the Ended event.
        -- This will make it so it won't play the next song until the current one
        -- has ended.
        Speaker.Ended:wait()

    -- End the for loop
    end

-- End the function
end

So with that covering everything I talked about initially, and applying this example, the final result should look like this:

local Songs = {309109778,304029790,243372213,417500483,281929968}
local Speaker = workspace:WaitForChild("Sound") -- I'd recommend using WaitForChild for this.

-- We'll call the function 'PlayRandomSounds'
local function PlayRandomSounds()
    local Songs = {unpack(Songs)}

    -- Iterate the copied table
    for i = 1,#Songs do

        -- Get, while also removing the randomly selected element
        -- since table.remove returns the element it removed, and we
        -- are indeed working with arrays, this is valid.
        local selected = table.remove(Songs,math.random(#Songs))

        -- Set the SoundId and play it
        Speaker.SoundId = selected
        Speaker:Play()

        -- And finally, use the wait method for the Ended event.
        -- This will make it so it won't play the next song until the current one
        -- has ended.
        Speaker.Ended:wait()

    -- End the for loop
    end

-- End the function
end

Hope this helped, if you have any questions, just let me know.

Here's how I did it, with detailed explanations:

local songs = { 309109778, 304029790, 243372213, 417500483, 281929968 }
local queue


local function playNextSong()
    -- If the queue doesn't exist or is empty, retrieve the songs' assetIDs
    -- from the songs list.
    if not queue or #queue == 0 then
        queue = { unpack(songs) }
    end

    -- Search script's children for a Sound object or create a new one
    -- if inexistant.
    local sound = script:findFirstChild("Sound") or Instance.new("Sound", script)
    local index = math.random(1, #queue)  -- Get a random element index from the queue.

    -- Retrieve the assetID of the music from the queue using the index.
    sound.SoundId = "http://www.roblox.com/asset/?id=" .. queue[index]

    -- Play the Sound object and wait until the sound.Stopped event is called.
    sound:Play()
    sound.Stopped:wait()

    -- Remove the song from the queue using it's index.
    table.remove(queue, index)
end


do
    -- Shuffle the songs. If we don't do that, the numbers returned
    -- by the random number generator might not be truly random.
    math.randomseed(tick())
    --
    -- See this for more informations:
    -- http://wiki.roblox.com/index.php?title=Random_numbers
    --
    -- Note: this might not work in Roblox Studio. It didn't
    -- really work during my testing, anyway.

    while true do
        playNextSong()
        wait(5)
    end
end