Random Map Generation Ideas Needed

For the map I'm currently working on (I'd like to keep exactly what it is a secret for the moment), I'd like to have at least some quantity of randomisation in the map. What do you guys think would be the best way to achieve this?
As I understand it, about all that can be done dynamically is the placement of destructibles and units/items, and terrain deformations (which won't affect pathing anyway, since it's only raise/lower ground, not cliffs).
Can any of you guys suggest what I could randomise apart from item placement in order to give more replayability?

Oh, and I will say one thing about my map: There are no heroes or buildings.
At all.

Destructables can affect pathing, so it is possible to generate things like routes dynamically. Depends somewhat on your environment though.

I always like to see maps with randomisation on its unit/creep, like a peon that as strong as a boss XD or an infrenal that as week as a sheep

Oh, there's only one kind of enemy, so that's out.
As for generating routes with destructibles... I know it's possible, but it's a real bitch to do anything more than just dynamically blocking/unblocking paths... Actually randomly generating an entire map is a little beyond me, and wouldn't fit the environment well anyway...

Well that's the basic theory behind random maze generation. Start with no paths between areas and 'unblock' random paths (as long as this doesn't open a path between two areas which are already joined by another path) until all areas are connected.

Yeah, I know, but it takes a hell of a lot of triggering/JASS that I'm pretty sure I'm not capable of...
'Course, I could steal someone else's maze generation algorithms, but I think that might cause trouble later... And as I've said, a maze doesn't really fit the map anyway...
Perhaps I should create some predefined groups of destructibles and terrain deformations and randomly populate the map using those?

It's really difficult for me to come up with any ideas without a concept for what the map is like.

The only thing I can think up is:
Randomly placed area buffs. (Auras that affect everyone.) In the area everyone gains certain advantages or disadvantages.
For example, in an area, all mana regeneration is increased by 1/sec, but units in the area take 33% more spell damage.
Or, in an area, all attack speeds are increased by 25%.

Etc.

Thanks, but I've actually just decided to randomly doodad the entire map; it was the terrain I wanted to randomise anyway.
Thanks anyway though.