I would do similar to the accepted answer but deal out a different number of piles that never are a multiple of the number of cards. Deal out the entire deck randomly as well to each of these piles, then combine the piles randomly always putting the next pile on the bottom or always putting the next pile on top. For example:
a deck of 80 cards should have the deck divided up by an odd number of stacks. We want the highest number we can take before it's too cumbersome. So say 7 stacks. 7 goes into 80 11 times with 3 left over. If you chose 9 stacks to deal out to then it would be 8 cards a stack with 8 left over. The numbers look more "messy" with the stack of 7 so let's go with it. Now you deal out randomly to each stack even keeping the piles uneven from the 11 increasing the imbalances of each stack. This adds even more randomness into the spread of the cards. Now you take each pile and combine them putting each stack on the bottom. There is no need to alternate top or bottom since you are choosing to pile the stacks randomly. Random is random, so it's faster to just keep it the same in one way but randomize it in your choice of what goes on the bottom.
The deck is now immediately shuffled. There is no reason to do any other type of shuffle. All the cards have been spaced out from each other by at least 7 spaces from their original position and with your randomness you increase or decrease that spacing randomly throughout. Then you stacked the spacing randomly again which gives 3 levels of randomization to the shuffle: the 7 spacing, the random up/down of spacing and the random piling. The faster you deal out the cards to the stacks, the faster this will finish but you will always have a complete shuffle with no need to do any other type of shuffle. Cutting the deck after is totally acceptable and encouraged.
EDIT: It takes me 30s to shuffle a 52 card deck in this way. Shuffling with 14 stacks, only added 15s to the time. The more stacks the better but this will undoubtedly shuffle the deck without damaging the cards.