Many a dentist has told me that toothpaste isn't necessary. I believe it became popular through effective advertising and the idea that the minty/tingly feeling made people believe that their mouth was clean, which is what the advertisers promoted (I actually read that in a book . . . I think it was [I]Super Freakonomics[/I]). You can brush with just the brush if you like and will have the same effect!
Any dentist I've spoken to has said if you can only either floss or brush, it is better to floss (cleans your gums as opposed to just your teeth). I'm guessing people are like our pets though, in that if you are consuming / eating things will small bones you are probably giving your teeth a clean - I'm not sure I'm prepared to stop brushing / flossing to try out that theory though!!