My suggestion for a way to randomize the starting positions (also works with all shuffles) and also record this position in a way that is self-explanatory for the nature of the positions.  Please feel free to comment. 

Need 8 cards or tiles numbered 1-8.
These cards or tiles represent columns on a chessboard.  Numbers are used instead of letters, for notation purposes (see below).  Numbers correspond to different columns. 1=A, 2=B, 3=C, 4=D, 5=E, 6=F, 7=G, 8=H .   The space the pieces would go in are in the row they would normally set up in.  In normal chess, white goes into row 1 and black in row 8.  

Will place pieces in following order: Bishops, King, Rooks, Queen, Knights.  Pawns remain where they normally should be.  Whenever a card has been picked, then that card is separated from remaining cards to be used to determine placement of pieces.

To place Bishops: Separate cards into odd and even piles.  Shuffle and deal out one from each.  First place odd, then even numbers.  Record these two numbers. Example: Card 5 and card 6 came up.  Bishops are put in columns E (card 5) and F (card 6).  Record first two digits as 56

To place King: Gather together all cards that were not selected. Separate 1 and 8 cards from these cards. If the 1 card was already selected, then separate out the 2 card.  If the 8 card has already been selected, then separate out the 7 card.  These cards will be added back in to select placement of Rooks and Queen.  Shuffle together these remaining cards, and select 1.  Record this number.  Example: Card 3 came up.  Rook is put in column C (card 3).  Next digit is recorded as a 3.  The current record of pieces placed is 563.

To place Rooks: Look at position of King.  Gather together all remaining cards in a lower position than position of King in one pile (following with example here, cards 1 and 2) and all remaining cards in a higher position than King (following the ongoing examples, this would be cards 4, 7, 8).  Random select from first pile one card (or if there is only one card, then that is the position), and from second pile one card.  Record these numbers (lower then higher), and place rooks in these columns.  In this ongoing set of examples, let's say 2 and 8 were selected.  The numbers two and 8 would be recorded with the other numbers, and Rooks placed in the B (card 2) column and H (card 8) column.  The current record of pieces would be 56328

To place Queen: Take remaining cards together shuffle, and select one.  Queen would go in that column.  In this ongoing example, the remaining cards would be 1, 4, 7.  For this example, say the 1 card was picked.  Queen would be placed in the A column (card 1).  The current record would be 563281.  This is the final recorded position.

To place the Knights:  Place them in the two remaining empty positions.  In the ongoing example here, the remaining cards would be 4 and 7.  The Knights are placed in columns D (card 4) and column G (card 7).

To sum up, the position generated by this is: 564281 (b56 k3 r28 q1).  This is also the notation name for the position. 

Board set up would look like this:
qrknbbnr
pppppppp

[Empty spaces between pieces]

PPPPPPPP
QRKNBBNR

-------------------------------------
For a more random shuffle, in games without castling, the order of the pieces is done the same, but with less restrictions.  For color balance of Bishops, the same idea of sorting the cards by odd or even would apply.  Bishops would be then put on appropriate spaces.  Say 1 and 8 were picked.  The notation would be: 18 for Bishops.

Then the King would placed.  Say 2 was picked.  Notation would be 182

Then the Rooks would be placed.  Say 5, 7 were picked.  Notation would be so far 18257

Then the Queen would be placed.  Say position 3 was picked.  Notation would be 182573

Knights would be placed in empty spaces.

Pieces would be in following configuration:
BKQNRNRB

Final notation for this position is: 182573