I'm looking for MIDI sequencing software that will allow me to easily
and successfully re-order parts, tempos, and time signatures.

Let me start out by saying that I am not a classicly trained musician.
 I don't know a whole lot about music theory, but I enjoy writing
music.  Lately, i've been experimenting with composing songs with lots
of time-signature and tempo shifts, and found it necessary to lay out
a MIDI template of sorts to help me with my song writing process. 
Unfortunately, I've found it difficult to successfully do this with
the two pieces of software I own:

Cubase SX3 and Cakewalk Sonar 5

Cakewalk Sonar 5:

When using Cakewalk Sonar 5 I've found it extremely frustrating when
it comes to being able to easily change and organize time-signatures. 
When I attempt to compose a song, I first add a single MIDI track, add
some notes in the staff view, and change the time signature when
needed.  When i've assembled a nice multi-tracked MIDI groove, I'll
move on and start a new part.  When i've created a few parts that seem
to work together, I'll begin to think about re-arranging parts.  This
is where Cakewalk fails for me.  Being able to copy all of the notes,
as well as the time signature and tempo information, should be easy
but cakewalk can never paste it without incorrectly shifting
everything into chaos.  Cakwalk Sonar 5 includes a time signature list
that allows you to edit and insert per measure, but it doesn't allow
you to mass move time signatures to make up for it's tendency to
shift.  Those problems aside, it works fine if you already have your
song planned out before you start sequencing, but this is not how I
work.

Things I like about Cakewalk:

The staff view scrolls to the right infinitely.  Other software seems
to move down after hitting the edge of the screen ( like real sheet
music ), but I actually don't like this.

Cubase SX 3:

Cubase SX's staff view ( or score view, as they call it ) seems to be
more accustomed to how REAL composers might work.  The staff moves
down the page, which as I said, I don't like and I just find it very
difficult to look at in general.  Whenever you have a note selected
there is a distracting white spot on the note head, which sometimes
keeps you from being able to tell what you're looking at. I could deal
with only using the Key Editor, but you can't view multiple tracks at
once and it has no access to editing time signatures.  Perhaps there
are work arounds, but there are enough MIDI quirks that keep me from
using Cubase for anything other than audio recording.

Things I like about Cakewalk:

Everything audio related

I've tried a few other trial versions of software ( Band in a box,
midiNotate Musician, Sibelius (OSX only, but I don't like it anyway) )
without luck.

With that said, I am basically looking for sequencing software that is
more accustomed to someone who is more experimental.  I want to be
able to shift compositions around with ease, copying parts and their
respective time signatures and tempos, knowing that they will remain
intact when I plop them elsewhere on the timeline. I don't need any of
the tradional music symbols and such, because I won't be printing
anything out for anyone to play.  Does such software exist?

I'd say Cubase is pretty much what you're looking for.  It's not a
quick program to learn, but it will do most everything you're trying
to do and it's not difficult once you've got the basics down.  In my
opinion, the score view in Cubase is not the best way to accomplish
what you're trying to do, however.  That view is really for people who
ARE classically trained (you mentioned that you aren't).  If you're
mostly interested in experimenting and moving things around, you'd be
better off using the standard MIDI view.

Pro Tools is my software of choice, and although it's not quite as
advanced in the MIDI department as Cubase, it's an extremely efficient
and powerful piece of software once you get the basics down.

My best recommendation would be to find someone who really knows
whatever software you've decided to use and hire them for an hour or
two to give you a quick tutorial.  Most of these applications can be
fairly byzantine in the early stages.  I struggled with Pro Tools on
my own for a while before finally asking an experienced engineer
friend to show me how to use it.  An hour of watching him and I had it
nailed.

You might also want to check out Propellerheads Reason.  There's a
good video tutorial on their site:

http://www.propellerheads.se/news/articles/index.cfm?fuseaction=get_article&article=video