Well, it isn't yew, and it isn't laburnum. Bark is wrong for both, as is colour of wood and lack of heart wood.
Just to throw everyone, it is possible, from the little info available, that it could be some kind of gum tree? The rings seem quite wide, and the great length with few branches sound right for something that grows fast, even if the bark looks a bit wrong.
If I had to put money on something native though, I would go with hornbeam, grown in a dark wood. The bark looks about right, hornbeam is sometimes called "ironwood", in the right places it can grow tall, spindily and straight. I always thought it was a little whiter, but can't say that I have seen any seasonned stuff that big up close.
Nice puzzle!
As for carving. Don't give up, just change tactics! If it is too hard to whittle, use saws, chisels and rasps! I have made a couple spoons from box wood, very hard, using rasps and files. Its nice to whittle something with only a knife, but that is a bit big to be doing a "bushcraft" spoon, I don't think there is any shame in using carpentry tools to make something beautiful from it. Good luck