As mentioned many times before, character creators are nice to play with and usually help the game in one aspect or another, but it's not the defining feature of RPG's. When I think of RPG's, there are two main blends for me. Either I make a character that I control and get to develop, or I control a premade character and act as they would act. The benefits of the character creator allow players to develop a character from the ground up, but when it comes to the plot, it has to be a lot more generic to accommodate all the different players there could be. With premade characters, the plot can be a lot more specific because no matter your play style, everyone plays the same character(s). A lot of those tend to blend into multiple genres, kinda like Fable being previously mentioned.
As far as Borderlands is concerned, I consider it a shooter with RPG elements, and Fallout 3 as an RPG with shooter elements. It's a simple turn of phrase, but the games are radically different.