How can you do C++ when your embedded compiler doesn't have operator new or STL support?

Question

I am working on a group senior project for my university and I have run into a major hurdle in trying to get my code to work.

The compiler that we have for our 8 bit Atmel microcontroller does not support the new or delete operators, and it does not support the C++ STL. I could program it in C, but I have to implement an A* algorithm which I have never done before. While I have tried C initially I soon realized that I never did pure C before. Trying to model objects with structs and functions is slowing me down since I am so used to the much cleaner C++ syntax.

Regardless, the exact wording for my compilers shortcomings can be found here: http://www.nongnu.org/avr-libc/user-manual/FAQ.html#faq_cplusplus

To overcome them and still use C++ I have considered the following possibilities. 1) Don't allocate anything, just use templates to generate fixed arrays on the stack. 2) Allocate and find some hack to call the constructor for objects once I have allocated the space for them. Placement new isn't an option since new isn't an operator. 3) Just use C and suck it up, its a microcontroller why am I getting fancy? 4) Find a better compiler which will probably cost $$$.

The second option is the hardest but it would have the biggest pay off in terms of how I can write this code. However, I imagine that debugging it could be a huge pain if I get it wrong. I'm thinking of creating objects on the stack, copying their bits into the allocated space, and then zeroing the bits in the object so it doesn't call its destructor. To do that I would access the bits directly with an unsigned char pointer and the sizeof operator to get the byte count.

That sounds terrible and I don't know if it could work reliably, but I am considering it. I know vtables can be a problem but I don't intend on having any vtables since it is just an 8 bit microcontroller.